Xreferat.com » Рефераты по математике » Численные методы

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

ЛЕКЦИЯ №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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

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