§ 2. Интерполяционный многочлен Лагранжа

Среди способов интерполирования наиболее распространен случай линейного интерполирования: приближение ищется в виде

где — фиксированные функции, значения коэффициентов определяются из условия совпадения с приближаемой функцией в узлах интерполяции :

Метод решения задачи, при котором коэффициенты , определяются непосредственным решением системы (1), называется методом неопределенных коэффициентов.

Как правило, в методе неопределенных коэффициентов число заданных условий равно числу свободных (неизвестных) параметров, подлежащих определению.

Наиболее изучен случай интерполирования многочленами

Тогда

и система уравнений (1) имеет вид

Далее мы предполагаем, что все различные. Определитель этой системы отличен от нуля (определитель Вандермонда). Следовательно, система (3) всегда имеет решение, и притом единственное. Таким образом, доказано существование и единственность интерполяционного многочлена вида (2).

Непосредственное нахождение коэффициентов с помощью решения этой системы уже при сравнительно небольших , например, при , приводит к существенному искажению коэффициентов вычислительной погрешностью. Кроме того, как мы увидим в гл. 4, уже сама запись многочлена в традиционной форме (2) часто приводит к большой вычислительной погрешности результата. При теоретических исследованиях, например при конструировании алгоритмов решения других задач, эти обстоятельства могут не играть роли. Однако при реальных вычислениях влияние вычислительной погрешности может быть недопустимо большим, и поэтому применяются другие виды интерполяционного многочлена и способы его записи.

Можно получить явные представления интерполяционного многочлена (2), не прибегая к непосредственному решению системы (3). Сразу же отметим, что в других случаях, например при функций многих переменных, получение интерполяционного многочлена в явном виде затруднительно, и часто приходится прибегать к непосредственному решению системы уравнений типа (1).

Пусть есть символ Кронекера, определяемый соотношениями

Задача интерполирования будет решена, если удастся построить многочлены степени не выше такие, что при . Многочлен

будет искомым интерполяционным многочленом. В самом деле,

кроме того, — многочлен степени .

Поскольку при , то делится на при . Таким образом, нам известны делителей многочлена степени , поэтому

Из условия получаем

Интерполяционный многочлен (2), записанный в форме

называют интерполяционным многочленом Лагранжа.

Существуют другие формы записи того же интерполяционного многочлена (2), например рассматриваемая далее интерполяционная формула Ньютона и ее варианты. При точных (без округлений) вычислениях значения, получаемые по различным интерполяционным формулам, совпадают. Наличие же округлений приводит к различию в получаемых по этим формулам значений интерполяционных многочленов. Запись многочлена в форме Лагранжа, как правило, приводит к меньшей величине вычислительной погрешности; запись же многочлена в форме Ньютона более наглядна и позволяет лучше проследить аналогию проводимых построений с основными построениями математического анализа. Кроме того, этим различным формам записи соответствует различное количество арифметических операций при вычислении с их помощью значений интерполяционного многочлена.

Мы употребили термин «количество арифметических операций». Поясним, что имеется в виду. Пусть рассматривается задача вычисления значения многочлена

в точке . Вычисления можно проводить различными способами. Например, можно поступить следующим образом. Вычислить значение и сложить с . Далее вычислить значение и сложить с полученным результатом и т.д. На шаге, таким образом, вычисляется значение и складывается с уже вычисленной суммой .

Вычисление значения требует j операций умножения. Таким образом, описанный выше алгоритм требует для вычисления значения моногочлена операций умножения и операций сложения. Количество арифметических операций (действий) в данном случае будет равно .

Ясно, что количество арифметических операций, необходимых для вычисления значения , может быть уменьшено. Например, можно последовательно вычислить и запомнить значения . Для этого потребуется операций умножения. Далее вычисляем величины . Это потребует операций умножения. Складывая полученные значения (это требует операций сложения), получаем . В этом случае и уже при имеет место неравенство .

Можно пойти еще дальше. Запишем в виде

Для вычисления значения во внутренних скобках требуется одна операция умножения и одна операция сложения. Для вычисления значения в следующих скобках требуется опять одна операция умножения и одна операция сложения, так как уже вычислено, и т.д. Таким образом, вычисление при помощи этого алгоритма потребует операций умножения и операций сложения, то есть .

Ясно, что при . Таким образом, вычисление по последнему алгоритму потребует меньше арифметических операций и, соответственно, меньше времени ЭВМ. Количество арифметических операций, которое требуется для получения результата, является одной из важнейших характеристик метода, по которой происходит сравнение методов.

Иногда до начала вычислений не удается точно оценить требуемое количество арифметических операций, а удается оценить лишь порядок количества арифметических операций по отношению к какому-либо параметру. В рассматриваемом выше примере

— степень многочлена.

В последнем случае говорят, что методы имеют одинаковый порядок количества арифметических операций.

В тех случаях, когда находится порядок количества арифметических операций, бывает важно найти постоянную в главном члене. Например,

Как правило, метод, требующий меньшего количества арифметических операций, является более быстрым, и поэтому считается лучшим. Выбирая метод решения сложных задач, часто ограничиваются лишь сравнением порядков количества арифметических операций для различных методов.

Заметим, что значение многочлена определяется параметрами и величиной . Поэтому в общем случае для вычисления потребуется не менее арифметических операций, т.е. мы имеем оценку снизу для количества арифметических операций. Таким образом, второй и третий методы вычисления являются оптимальными по порядку, так как и для любого метода .

В связи с появлением многопроцессорных вычислительных комплексов может случиться так, что метод, требующий большего количества арифметических операций, будет быстрее другого метода с меньшим количеством арифметических операций. Поэтому для случая многопроцессорной ЭВМ нельзя оценивать качество метода только по количеству арифметических операций.