Методы компьютерных вычислений и их приложение к физическим задачам

Блок-схема алгоритма метода Гаусса без выбора главного элемента.

Итерационные методы решения систем линейных уравнений.

Простейшим итерационным методом решения СЛАУ является метод простой итерации. При этом система уравнений (1) преобразуется к в

иду (2), а ее решение находится как предел последовательности (3), где {n} – номер итерации. Утверждается, что всякая система (2), эквивалентная (1), записывается в виде .

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

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

На практике для обеспечения сходимости итерационных методов необходимо, чтобы значения диагональных элементов матрицы СЛАУ были преобладающими по абсолютной величине по сравнению с другими элементами.

Представим СЛАУ в следующей форме, удовлетворяющей (3):

(4)

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

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

Критерий сходимости метода Зейделя: Пусть – вещественная симметричная положительно определенная матрица. Тогда метод Зейделя сходится.

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

8)Интерполирование функций.

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

Условия Лагранжа : ф(х, с0, с1…сn) = fi,

0 <_i < n, где сi - свободные параметры, определяемые из данной системы уравнений.

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

приближения).

2) Пусть ф (х) = с0 + с1х + с2х2 +…+ сnxn (канонический вид полинома) ;сетка узлов может быть неравномерной.

Коэффициенты сi определяются из условий Лагранжа:

Получившаяся СЛАУ относительно свободных параметров сi имеет решение, если среди узлов хi нет совпадающих.Ее определитель – определитель Вандермонда:

Общая блок-схема:

3) Пусть задано n+1 значение функции f(x) в узлах xj

ф(х) = Pn(х) = i (x-xj)/(xi-xj) - полином Лагранжа.

Преимущества: потребуется решать СЛАУ для определения значения полинома в точке х.

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

Погрешность формулы: (*)

Увеличение числа узлов и, соответственно, степени полинома Pn(x) ведет к увеличению погрешности из-за роста производных .

4) ф(х) = Pn(x) = A0+A1(x-x0)+A2(x-x0)(x-x1)+…+An(x-x0)(x-x1)…(x-xn-1) - многочлен Ньютона для n+1 узла.

Коэффициенты Ф представляют собой разделенные разности и записываются в виде:

А0 = f0

A1 = (f0-f1)/(x0-x1) = f01

A2 = (f01-f02)/(x1-x2) = f012, где f02 = (f0-f2)/(x0-x2)

A3 = (f012-f013)/(x2-x3) = f0123 , где f013 = (f01-f03)/(x1-x3) , а f03 = (f0-f3)/(x0-x3)

и в общем случае Ak = (f01…k-1-f01…k)/(xk-1-xk)

Т.е. многочлен n-й степени выражается при помощи разделенных разностей через свои значения в узлах.

Преимущества: не решается СЛАУ, однако вычисление коэффициентов полинома не зависит от значения х и может быть вычислено только один раз. При добавлении нового узла также не происходит пересчета коэффициентов, кроме последнего.

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

P2(x) = A0+ (x-x0)(A1+(x-x2)(A3+…)…)

Погрешность определяется тем же соотношением (*)

Входящая в состав погрешности величина

(х-хi) = wn(x) ведет себя при постоянном шаге так, как показано на рисунке. Многочлен Ньютона имеет погрешность 0(hn+1) и обеспечивает n+1-й порядок точности интерполяции.

! Между разделенными разностями и производными соответствующих порядков существует соотношение f <n>(x) ~ n! F01…n , где n – степень производной. Это используется в численном дифференцировании и при оценке погрешностей интерполяции.

! Можно строить полиномы, не только проходящие через заданные точки, но и имеющие в них заданные касательные (интерполяционный многочлен Эрмита) или заданную кривизну. Количество всех полагаемых условий должно быть n-1, если n – степень полинома.

 Скачать реферат