ВМ (Ответы на экзаменационные вопросы в виде шпаргалки), страница 3

В результате данного преобразования перейдем к СЛАУ

имеющей в матричной форме следующий вид:

где f - матрица Якоби.

Предположим, что матрица Якоби невырожденная, то есть существует обратная матрица

Тогда система (6) имеет единственное решение, которое принимается за очередное приближение x^(k+1) к решению x, то есть приближение x^(k+1) удовлетворяет равенству

выразив из полученного равенства x^(k+1), получим формулу метода Ньютона:

где A_ij - алгебраическое дополнение элемента a_ij.

M_ij - минор элемента a_ij , то есть определитель порядка n - 1, получающийся из A вычеркиванием i - ой строки и j - го столбца.

Сходимость метода.

Теорема. Пусть в некоторой окрестности решения x системы (1) функции f₀(i=1,n) дважды непрерывно дифференцируема и матрица f (x) невырождена. Тогда найдется такая малая ... -окрестность решения x, что при произвольном выборе начального приближения x⁽⁰⁾ из этой окрестности, итерационная последовательность метода Ньютона не выходит за пределы окрестности и справедлива оценка:

метод сходится с квадратичной скоростью.

Критерий окончания процесса.

ВОПРОС №9. Вопросы приближения функций. Постановка задачи. Понятие точной и интерполяционной аппроксимации. Интерпретационный многочлен Лагранжа. Теорема о единственности.

Приближение функций. Постановка задачи. Если величина y является функцией аргумента x, то любому значению x из области определения y будет поставлено в соответствие значение y. Однако, на практике часто неизвестна явная зависимость y от x, то есть ее невозможно записать в виде y = f(x). Бывают случаи, когда затруднительно использовать даже известную зависимость f(x).

Наиболее распространенным случаем, когда вид связи между параметрами y и x неизвестен, является задание этой зависимости в виде таблицы {x_i,y_i}. В этом случае дискретному множеству значений аргумента соответствует множество значений функции {y_i}, i = 1,n. Эти значения получены либо в результате расчетов, либо в результате экспериментов.

Нам могут потребоваться значения функции y и в других точках, = x_i. Однако получить их можно лишь путем сложных расчетов или дорогостоящих экспериментов

Таким образом, мы приходим к необходимости использования имеющихся табличных данных для приближенного вычисления значения y при любом значении параметра x, так как точная связь y = f(x) неизвестна.

Этой цели служит задача аппроксимации функции: функцию f(x) требуется приближенно заменить некоторой функцией ...(x) так, чтобы отклонение ...(x) от f(x) в заданной области было наименьшим. Функция ...(x) при этом называется аппроксимирующей.

Для практики весьма важен случай аппроксимации функции многочленом:

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

Если приближение строится на заданном дискретном множестве точек {x_i}, то аппроксимация называется точечной. При построении приближения на непрерывном множестве точек аппроксимация называется непрерывной (интегральной).

Точечная аппроксимация.

Одним из основных типов точечной аппроксимации является интерполяция. Она состоит в следующем: для заданной функции y = f(x) строится многочлен, принимающий в заданных точках x_i те же значения y_i, что и функция f(x), то есть

При этом предполагается, что среди значений x_i нет одинаковых, то есть x_i = x_j при i = j. Точки x_i называются узлами интерполяции, а многочлен ...(x) - интерполяционным многочленом.

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

Максимальная степень интерполяционного многочлена m = n; в этом случае говорят о глобальной интерполяции, так как один многочлен

используется для интерполяции функции f(x) на всем рассматриваемом интервале изменения аргумента x_i . Коэффициенты a_j многочлена находятся из системы уравнений y_i=...(x_i, i = 1,n). При x_i = x_j ( i = j ) эта система имеет единственное решение.

Как правило, интерполяционные многочлены используются для аппроксимации функции в промежуточных точках между крайними узлами интерполяции, то есть при x₀ < x < x_n.

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

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

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

Многочлен Лагранжа.

Перейдем к случаю глобальной интерполяции, то есть построению интерполяционного многочлена, единого для всего отрезка [x₀, x_n]. При этом график интерполяционного многочлена должен проходить через все заданные точки.

Запишем искомый многочлен в виде:

Из условий равенства значений этого многочлена в узлах x_i соответствующим заданным табличным значениям y_i, получим систему уравнений для нахождения коэффициентов a₀, a₁,...,a_n:

Эта система имеет единственное решение, если среди узлов интерполяции нет совпадающих, то есть, если x_i x_j при i j. Решив эту систему, найдем коэффициенты интерполяционного многочлена. Заметим, что такой путь построения многочлена может потребовать больших вычислений, особенно при большом числе узлов.

Рассмотрим более простой алгоритм построения интерполяционных алгоритмов. Будем искать многочлен в виде линейной комбинации множеств степени n.

При этом потребуем, чтобы каждый многочлен l_i (x)=0 во всех узлах интерполяции, за исключением одного (j-го), где он = 1. Легко проверить, что этим условиям отвечает многочлен вида:

Действительно, l₀(x) = 1 при x = x₀. При x = x₁, ... , x_n числитель выражения = 0. По аналогии получим:

Подставив эти формулы в исходный многочлен получим:

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

Докажем, что этот многочлен является единственным. Допустим противоположное: пусть существует еще один многочлен F(x) степени n, принимающий в узлах интерполяции заданные значения, то есть F(x_i) = y_i, i = 0,n. Так как F(x_i) = y_i и L(x_i) = y_i, то разность R(x) = L(x) - F(x), являющаяся многочленом степени n (или ниже), в узлах x_i равна:

Если R(x)=L(x)-F(x) 0, то разность R(x) (будучи многочленом не выше n-й степени- это следует из вида многочлена L(x), в котором n+1 слагаемое, каждое по n множителей), в силу основной теоремы высшей алгебры имеет не более n корней.

[Основная теорема алгебры: каждое алгебраическое уравнение n-й степени

коэффициенты, которого a₁,a₂,...,a_n - действительные или комплексные числа, имеет ровно n корней действительных или комплексных.]

Это противоречит равенствам:

число, которых равно n + 1 (система из (n+1)-го уравнения).

Возникло противоречие: многочлен, который не может иметь более n корней, имеет n+1 корень. Следовательно, многочлены L(x) и F(x) тождественны (L(x) F(x)).

Из формулы интерполяционного многочлена Лагранжа

можно получить выражения для линейной и квадратичной интерполяции:

ВОПРОС №10. Вопросы приближения функций. Постановка задачи. Многочлен Ньютона с распределяющими разностями.

Приближение функций. Постановка задачи. (ВОПРОС №9)

Многочлен Ньютона с распределенными разностями.

Пусть некоторая функция f(x) задана таблицей своих значений {x_i;f(x_i} с произвольным размещением узлов интерполяции.

Разделенными разностями первого порядка принято называть величины:

Разделенные разности второго порядка можно вычислить по формуле:

Т.о, разделение разности k-го порядка можно найти по формуле:

Составим таблицу распределенных разностей:

Разделительные разности обладают след. св-ми:

Свойства разделенных разностей.

1). разделительная разность f ( x_i; x_i+1;x_i+k ) является симметричной функцией своих аргументов x_i,x_i+1,x_i+k (не изменяется относительно любой их перестановки);

2). пусть функция f (x) на отрезке [a;b], содержащем точки x_i,x_i+1,x_i+k, производную порядка k. В этом случае:

Любая функция, непрерывная на [a;b] и имеющая на этом отрезке производные, включая k-ю, может быть разложена в ряд Тейлора:

Используя свойства распределенных разностей запишем интерполяционный многочлен Ньютона с распределенными разностями:

ВОПРОС №11. Вопросы приближения функций. Постановка задачи. Многочлен Ньютона с конечными разностями для интерполяции вперёд.

Приближение функций. Постановка задачи. (ВОПРОС №9)

Многочлен Ньютона с конечными разностями для интерполяции вперёд.

В рассмотренных выше методах не делалось никаких предположений о законе распределения узлов интерполяции. Рассмотрим случай равноотстоящих узлов интерполяции, то есть x_i - x_i-1 = const = h, i=2n. h - называется шагом.

Введем понятие конечных разностей. Пусть известны значения функции в узлах x_i : y_i = f(x_i ). Составим разности значений функции: