Рефетека.ру / Математика

Учебное пособие: Численные методы

ЛЕКЦИЯ №5


МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ

СНУ


Пусть дана система вида:

Численные методы (5.1)

f'(x)=Численные методы - производная

Численные методы

Частная производная Численные методы- вектор (все значения).


МЕТОД НЬЮТОНА

Дана система вида (5.1), где fi один раз непрерывно дифиринцируемые функции, т.е. существуют все частные первые производные этих функций.

Строим последовательность приближенийЧисленные методы сходящуюся к точному решению системы Численные методы.

Пусть Численные методы - некоторое начальное приближение к решению, а Численные методы- катое приближение к решению. Построим зависимость, позволяющую на основании Численные методы построить Численные методы.

Точное приближение Численные методы

Численные методы

ξ-корень обращает уравнение в верное равенство(тождество).

Численные методы (5.2)

Разложим функции fi из системы (5.2) в ряд Тейлора в окрестности точки хк до линейных составляющих.

Численные методы (5.3)

Система (5.3) представляет собой систему линейных алгебраических уравнений для поиска компонента вектора поправки hk.

Перепишем систему (5.3) в виде:

Численные методы (5.4)

Численные методы

Сокращаем запись системы (5.4) : Численные методы (5.5)

Решим систему (5.5) методом обратной матрицы. Определитель Якобиана в точке хк не равен 0.


Численные методы

Получили связь последующего приближения с предыдущим.

Численные методы (5.6)

Численные методы Численные методыусловие окончания вычислений. (5.7)

Численные методы- расстояние между векторами (метрика).

МЕТОД ИТЕРАЦИЙ

Пусть дана система вида (5.1). Преобразуем ее к видуЧисленные методы (5.8)

Система (5.8) в векторном виде Численные методы (5.9)

Необходимо найти неподвижную точку систему Численные методы

Очевидно, что эта точка ξ – решение системы (5.1)

Пусть дано Численные методы-некоторое начальное приближение к ξ и на k-том шаге получено приближение Численные методы. Тогда последующее приближение :

Численные методы (5.10)

Условие окончания совпадает с (5.7)

Всегда ли метод сходится?

Пусть М- матрица, составлена из элементов mij

M=[mij], где mij=Численные методы

Определение нормы матрицы А: Численные методы-число удовлетворяющее свойствам.

1) Численные методы≥0, Численные методы=0Численные методыЧисленные методы≡0

2) Численные методычисло

3) Численные методы

4) Численные методы

Способы задания нормы матрицы:

1) Численные методы=Численные методы

2) Численные методы=Численные методы

3) Численные методы=Численные методы

Достаточное условие сходимости метода итераций:

Если Численные методы, i=1,n , Численные методына Сч и Численные методыЧисленные методыСч, то процесс итераций сходится независимо от выбора начального приближения.


МЕТОД ЗЕЙДЕЛЯ


Пусть дана система вида (5.1), преобразуем ее к виду (5.8). Как и в методе итераций строим последовательность приближений Численные методы к неподвижной точке.

Численные методы

ускорение сходимости за счет подстановки предыдущего приближения.

Достаточное условие совпадает с достаточными условиями сходимости метода итераций.

Условие окончания получения приближений совпадает с (5.7).

ЛЕКЦИЯ № 6, 7


ПРИБЛИЖЕНИЕ ФУНКЦИИ


Общая постановка задачи.

Пусть ¦(c) – некоторая функция, которая может быть известно, частично известной и неизвестной. Эту функцию необходимо заменить некоторой «хорошей» функцией j(c), которая будет достаточно близкой ¦(c).


Постановка задачи интерполяции.

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

что известно о ¦(c) (способ задания, степень гладкости);

к какому классу, семейству функций должна принадлежать j(c);

что понимаем под близостью j(c) и ¦(c) каков критерий согласия;

Часто приближение функции называют аппроксимацией

Постановка задачи интерполяции.

Пусть ¦(c) задана на некотором разбиении отрезка [a;b] точками хi ,

i=0,n , где a = х0<х1<…<xn= b

интерполяция – вычисление ¦(c) в точке О[a;b], x № xi, i = 0,n

экстраполяция – вычисление функции ¦(c) в точке ХО[a;b];

Определение интерполяции ввел в 1656 году Джон Уолесс, а в 1655 году ввел символ Ґ.

Для полиномиальной интерполяции j(c) имеет вид j(c)=а0+а1х+а2х2+…+аnxn.

Для того, чтобы считать j(c) к ¦(c) вводится ограничение j(ci)= ¦(ci), i=0,n ;

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

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

Необходимо определить коэффициенты полинома степени n(их будет n+1), построения аппроксимации функции, заданной в n+1 узле. Используя ограничения на j(c): j(ci)= ¦(ci)=y, i=0,n , составим систему:

Численные методы (6.1)

Выпишем определитель этой системы

Численные методы


Определитель

Вандермонда


При условии: x0№xj при i№j определитель системы (6.1) отличен от нуля, следовательно, система имеет единственное решение.

Вывод:

если задано разбиение в виде n+1различной точки, то всегда существует функция в виде полинома n-ой степени, которая проходит через все точки графика ¦(c),определенной на этом разбиении.

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

Лагранж предложил строить интерполяционные полиномы в виде:

Pn(x)=∑ Ci li(x) (6.2)


Ci=yi=¦(ci), li(x)=полиномы n-ой степени, которые удовлетворяют условию:

Численные методы

Для полинома узлы интерполяции xj, j=0,n , j≠I являются корнями, причем действительными и попарно различными (все имеют кратность 1)

Тогда полином li может быть записан в виде:

Численные методы (6.3)


Общий вид полинома Лагранжа:

Численные методы (6.4)

Встает вопрос о точности, о приближения функции. Вводится понятие остаточного члена многочлена Лагранжа ; для того, чтобы оценить аппроксимации ¦(c) в некоторой точке x О[a;b]

Функцию ¦(c) представим в виде ¦(c)= Pn(x)+Rn(x), где Rn(x)- остаточный член многочлена Лагранжа в процессе длительного и трудоемкого вывода для Rn(x) получена следующая формула:

Численные методы (6.5)

Строится система вложенных отрезков

¦(n+1) -производная (n+1)-го порядка


Пусть Численные методы

Численные методы (6.6)

Если ¦(c)-полином n-ой степени, то производная (n+1)-го порядка равна 0, тогда Rn(x)≡0 и мы получаем точную аппроксимацию.

Теорема:

Многочлен Лагранжа вида (6.4) для таблично заданной функции единственен.

Доказательство:

Пусть Qn(x)- многочлен Лагранжа, построенный для этой же функции ¦(c) по тем же узлам интерполяции. Qn(x) №Pn(x) Qn(xi)=yi=Pn(xi), Численные методы

Рассмотрим многочлен Ln(x)= Qn(x)-Rn(x)-это многочлен n-ой степени, для которого точки xi , i=0,n являются корнями. Это противоречит основной теореме алгебры, которая говорит о том, что полином n-ой степени имеет ровно n корней . А Ln(x) имеет n+1 корней . Противоречие доказывает теорему.

Интерполяционная схема Эйткина

Поскольку при большом числе узлов интерполяции вычисление значения полинома Лагранжа по формуле (6.4) громоздко, необходимо получить рекуррентную формулу.

Пусть ¦(c)- непрерывна, узлы выбраны на отрезке [a;b] таким образом, что:

Численные методы

Введем функцию Численные методы

xi-узлы интерполяции;

yi=¦(c)

Численные методы

Полином Лагранжа: Pn (x) см. (6.4)

Численные методы

Таким образом, функция Q0,1 (x) представляет собой полином Лагранжа l-ой степени, построенной по узлам x0 ,x1 введем функцию вида

Численные методы

Функция Q1,2 (x)- интерполяционный полином Лагранжа, построенный по узлам x1 ,x2.

Введем теперь функцию

Численные методы

Аналогично:

Q0,1,2 (x2)= у2

В силу единственности полинома Лагранжа, построенного по узлам x0, x1 ,x2

функция Q0,1,2 (x) представляет собой интерполяционный полином Лагранжа 2-ой степени, построенный по узлам x0, x1 ,x2 .

Введем функцию:

Численные методы (7.1)

Функция представляющая собой полином Лагранжа 2-ой степени, построенного по узлам x0, x1,…xi.

Формула (7.1) позволяет рекуррентно вычислять полином Лагранжа любой степени.

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

(7.1)-интерполяционная схема Эйткина.


КОНЕЧНЫЕ РАЗНОСТИ


Пусть функция ¦(c) задана на системе равноотстоящих узлов xi=x0+ih, Численные методы

где h-шаг сетки, yi=¦(ci).

Конечной разностью первого порядка в точке x0 называется ∆y0=y1-y0

Конечной разностью первого порядка в точке xi: ∆yi=yi+1-y0-yi

Конечной разностью второго порядка в точке x0 : ∆2y0=∆y1-∆y0

Конечной разностью второго порядка в точке xi: ∆2yi=∆yi+1-∆yi


Общая формула для конечной разности k-того порядка в точке xi:

Численные методыЧисленные методыЧисленные методы

Численные методыkyi=∆k-1yi+1-∆ky (7.2)


Заметим: 0yi= yi

Формула (7.2) позволяет вычислять рекуррентно конечные разности

Связь конечных разностей и производных


Численные методы

чем меньше h, тем точность выше


Аналогично можем получить связь

Численные методы Численные методы; (7.3)

Свойства конечных разностей


В связи с производными вида (7.3) конечные разности обладают свойствами:

постоянные, равны нулю;

постоянный множитель у функции выносится за знак

суммы 2-х функций равны сумме каждой функции

полинома n-ой степени, n-го порядка постоянны и равны


∆ny=hnann!

an-коэффициент при xn полинома Rn(x)

Верно и обратное утверждение: все конечные разности n-го порядка некоторой функции постоянны и одинаковы, конечные разности n +1-го порядка равны 0, а конечные разности n-1-го порядка различны, то функция представляет собой полином n-ой степени.

Распространение ошибки в исходных данныхпри вычислении конечные разности


Любые измерения несут в себе погрешность (ошибка округления, точность измерения приборов)

Пусть значения функции определены в узлах x0, Численные методы и в некоторой точке xk значение некоторой точке xk значение функции найдено с ошибкой ε, т.е ỹk+ ε

Составим таблицу конечных разностей


xk-2 yk-2 ∆yk-2 ∆2yk-2 ∆3yk-3 + ε

xk-1 yk-1 ∆yk-1 + ε ∆2yk-2 + ε ∆3yk-2 -3 ε

xk yk+ε ∆yk-1 - ε ∆2yk-1 - 2 ε ∆3yk-1 + 3 ε

xk+1 yk+1 ∆yk+1 ∆2yk+ ε ∆3yk- ε

xk+2 yk+2 ∆2yk+1


Как видно из таблицы конечных разностей при увеличении порядка конечных разностей ошибка в исходных данных распространяется и растет.

Такое взаимодействие ошибок называют шумом, если это ошибки округлений - то шумом округлений.

Если ошибки округлений достаточно большие, то может происходить следующее явление: при увеличении порядка конечных разностей они могут уменьшаться и→0, но, дойдя до некоторого малого значения, опять могут начать расти из-за шума округлений.

Столбец в таблице конечных разностей, в которой все конечные разности ≈0, называют «практическим постоянным»; при этом конечные разности высших порядков не используют.

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

ЛЕКЦИЯ №8


ИНТЕРПОЛЯЦИОННАЯ ФОРМУЛА НЬЮТОНА ДЛЯРАВНООТСТОЯЩИХ УЗЛОВ


Дана функция y=¦(c),заданная на сетке равноотстоящих узлов:

yi=¦(ci), xi=x0+ihi, Численные методы


Строим интерполяционный полином с целью упрощения записи полинома (интерполяционного) и представления его в виде, позволяющем оценивать влияние каждого из компонентов на значение аппроксимации, запишем его так:


Nn(x)=-a0+a1(x-x0)+a2(x-x0)(x-x1)+…+an(x-x0)…(x-xn-1) (8.1)


Необходимо посчитать его коэффициенты ai. Будем находить из условия

Nn(xi)=yi Численные методы

i=0: Nn(x0)=y0=a0+a10+…+an0 a0= y0


i=1: Nn(x1)=y1= y0+a1(x1-x0) + a20+…+an0

Численные методы

x1=x0+1h=x1-x0=h


i=2: Nn(x2)=y2= y0+∆y0/h(x2-x0) (x2-x1) + a30+…+an0


x2-x0=2h

x2-x1=h

y2= y0+∆y02+a22h2


Численные методы

i=k: Численные методы (8.2)


Запишем теперь, используя (8.2), полином (8.1) в виде:


Nn(x)= y0+∆y0/h(x-x0)+…+ ∆n y0 /n!hn(x-x0)(x-x1)… (x-xn-1) (8.3)


Полином (8.3) 1-ый интерполяционный многочлен Ньютона. Он наиболее приспособлен для вычисления значения функции в точках, близких к x0

С целью упрощения записи полинома введем переменную Численные методы

x=x0+gh

Если g-целое, то будет совпадать с номером узла

x0 – базовый узел полинома (8.3)


xi=x0+gh- x0-ih=h(g-i);


Nn(g)= y0+∆y0g+…+ ∆n y0 /n!g(g-1)(g-2)(g-n+1) (8.4)


Полином Ньютона в силу единственности существования интерполяционного полинома Лагранжа является одной из форм записи полинома Лагранжа, поэтому для полинома (8.3) справедливо, что формула остаточного члена полинома Лагранжа


Численные методы

Для вычисления функции в точках находящихся в середине сетки узлов интерполяции либо в ее конце, т. е близкие к xn, применяют два подхода

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

формулы для точек х, близких к хn (упорядочивание узлов интерполяции).

Соответственно получаются формулы Стирлинга , Бесселя, Гаусса, и 2-ой интерполяционный многочлен Ньютона .

Второй путь: в качестве узла х0 для заданной точки х берут тот узел, который наиболее близок к х, узел х1 выбирают как самый близкий из оставшихся узлов к х.

Т.е последовательность Численные методыупорядочившаяся по возрастанию.

Для вычисления значения функции в точке х используется 1-ый интерполяционный многочлен Ньютона.

Численные методыЧисленные методыЧисленные методыЧисленные методыЧисленные методыЧисленные методыЧисленные методыЧисленные методы


х0 х1 х2 х3 х4 х5 х6

Преобразуем узлы:

х0′=x3;

x1′=x4 ;

x2′=x2 ;

x3′=x5 ;

Разделенные разности


Пусть функция ¦(c),задана на системе неравно отстоящих узлов.

Разделенной разностью 1-го порядка назовем выражение:

Численные методыЧисленные методы

Разделенной разностью 2-го порядка:

Численные методы

Разделенной разностью k-го порядка:

Численные методы (8.6)

|x-x0|, Численные методы


Свойства разделенной разности:

на сетке равноотстоящих узлов разделенной разности совпадают конечными разностями

разделенные разности понижают степень многочлена

разделенные разности n-го порядка постоянны и равны

Интерполяционная формула Ньютона для не равноотстоящих узлов

Пусть функция ¦(c), задана на сетке не равноотстоящих узлов xi, Численные методы.Запишем следующие разделенные разности:


Численные методы

Выполним такие действия n-1 раз, получим:

Численные методыПолином Ньютона:

Nn(x)= ¦0(c)

Rn(x)= ¦(c,c0,…cn)(x-x0)… (x-xn) (8.8)

То ¦(c)= Nn(x)+ Rn(x)

Nn(x) ≈ ¦(c)

Rn(x) = ¦(c) - Nn(x)

Если ¦(c) имеет (n+1)-ую производную, то остаточный член может быть преобразован к виду остаточного члена (8.9) полинома Лагранжа.

При вычислении полинома в точке х узлы интерполяции лучше переименовать так, чтобы х0 был самым близким к х, а все остальные узлы тем более удаленные по увеличению расстояния к х.

Похожие работы:

  1. • Экзаменационные билеты по численным методам за первый семестр ...
  2. • Численные методы интегрирования и оптимизации ...
  3. • Численные методы решения типовых математических задач
  4. •  ... высокого уровня для реализации численных методов
  5. •  ... высокого уровня для реализации численных методов
  6. • Решение прикладных задач численными методами
  7. • Численные методы анализа и синтеза периодических сигналов
  8. • Численные методы вычисления интегралов
  9. • Численные методы решения систем линейных уравнений
  10. • Вычисление площадей эпюр с использованием численных ...
  11. • Численные методы
  12. •  ... уровня для реализации численных методов и прикладных программ
  13. • Сравнительный анализ численных методов
  14. • Минимизация функции многих переменных. Приближённые численные ...
  15. • Визуализация численных методов
  16. • Численные методы
  17. • Шпаргалка по численным методам
  18. • Численные методы и их реализация в Excel
  19. • Факторизация в численных методах интегрирования вырожденных ...
Рефетека ру refoteka@gmail.com