Конспект лекций междисциплинарного курса МДК.01.04 Математические методы разработки алгоритмов профессионального модуля ПМ.01 Разработка программных модулей программного обеспечения для компьютерных систем (стр. 6 )

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

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

Существуют 3 класса или группы функций, широко применяемых в численном анализе. Первая группа включает в себя линейные комбинации функций 1, х, х2, …, хn, что совпадает с классом всех многочленов степени n (или меньше). Второй класс образуют функции cos aix, sin aix. Этот класс имеет отношение к рядам Фурье и интегралу Фурье. Третья группа образуется функциями e-az. Эти функции встречаются в реальных ситуациях.

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

3.1. Постановка задачи приближения функции

Пусть известные значения некоторой функции f образуют некоторую таблицу (табл. 3.1).

Таблица 3.1

			…
			…

При этом требуется получить значение функции f для такого значения аргумента x, которое входит в отрезок , но не совпадает ни с одним из значений (i = 0,1, …, n).

Очевидный прием решения этой задачи – вычислить значение f(x), воспользовавшись аналитическим выражением функции f. Этот прием, однако, можно применить лишь в случае, когда аналитическое выражение f пригодно для вычислений. Более того, часто аналитическое выражение функции вовсе неизвестно. В этих случаях применяется особый прием — построение по исходной информации (табл. 3.1) приближающей функции F, которая в некотором смысле близка к функции f и аналитическим выражением которой можно воспользоваться для вычислений, считая приближенно, что

f(x) = F(x).                                                (3.1)

Классический подход к решению задачи построения приближающей функции основывается на требовании строгого совпадения значений f(х) и F(x) в точках   (i = 0,1, …, n), т. е.

  (3.2)

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

Будем искать интерполирующую функцию F(x) в виде многочлена степени n

                (3.3)

Этот многочлен имеет n+1 коэффициент. Естественно предполагать, что n+1 условий (3.2), наложенных на многочлен, позволят однозначно определить его коэффициенты. Действительно, требуя для   выполнения условий (3.2), получаем систему из n+1 уравнений с n+1 неизвестными

  (3.4)

Решая эту систему относительно неизвестных , мы и получим аналитическое выражение полинома (3.3). Система (3.4) всегда имеет единственное решение, так как ее определитель, известный и алгебре как определитель Вандермонда, отличен от нуля.

Отсюда следует, что интерполяционный многочлен   для функции f, заданной таблицей 1.1, существует и единствен (может случиться, что какие-то коэффициенты в , в том числе и равны нулю; поэтому интерполяционный полином при рассмотренных условиях в общем случае имеет степень, не большую, чем n).

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

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

Пусть функция f задана таблицей 3.1. Построим интерполяционный многочлен Ln(x), степень которого не больше n и для которого выполнены условия (3.2). Будем искать Ln(x) в виде

                                       (3.5)

где li (x) –многочлен степени n, причем

                                                       (3.6)

Очевидно, что требование (3.6) с учетом (3.3) вполне обеспечивает выполнение условий (3.2).

Многочлены li (x) составим следующим способом

                (3.7)

где сi – постоянный коэффициент, значение которого найдем из условия (3.6)

(ни один множитель в знаменателе не равен нулю).

Подставим сi в (3.7) и далее с учетом (3.5) окончательно имеем:

                       (3.8)

Эго и есть интерполяционный многочлен Лагранжа. По таблице исходной функции f формула (3.8) позволяет весьма просто составить «внешний вид» многочлена.

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

Для составления программы вычисления одного значения интерполяционного многочлена Лагранжа на компьютере воспользуемся формулой (3.8). Основная рабочая часть искомого алгоритма состоит из вложенного цикла: во внутреннем цикле вычисляются n+1 значений многочленов-слагаемых вида li(x) (i = 0,1, ..., n),

а во внешнем – накапливается общая сумма (3.8).

Работа внутреннего цикла контролируется с помощью индекса j. Изменяясь в пределах от 0 до n, индекс j принимает все-таки ровно n значений, «проскакивая» текущее значение индекса i, определяемого во внешнем цикле. Тем самым обеспечивается правильное составление многочленов-слагаемых li(x) формулы Лагранжа. Носителем окончательного результата является переменная F. Схема алгоритма изображена на рис. 3.1.

               

                 

                        да                         нет

                                                        |

Рис. 3.1. Схема алгоритма вычисления значения интерполяционного многочлена Лагранжа

4. Решение систем линейных алгебраических уравнений (СЛАУ) 

4.1. Матрицы и их свойства Матрица – это совокупность чисел, расположенных в виде прямоугольной таблицы. Чтобы отличать матрицу по внешнему виду от определителя, ее заключают в квадратные скобки. Каждый элемент матрицы снабжают двумя индексами: первый соответствует номеру строки, второй – номеру столбца. Матрицу называют квадратной, если число строк в ней равно числу столбцов Диагональной называют матрицу, у которой элементы главной диагонали не равны нулю, а все остальные – нули, например:   Матрицу, у которой элементы главной диагонали равны единице, а все остальные – нули, называют единичной: Неопределенной называют матрицу, у которой сумма элементов любой строки и любого столбца равна нулю. Две матрицы равны, если равны соответствующие элементы этих матриц. У равных матриц равны определители. Но из равенства двух определителей еще не следует равенства самих матриц.

4.2. Выполнение операции над матрицами