Теорема Самарского о сходимости стационарных методов

Теорема. Пусть,и, тогда итерационный процесс

(3.15)

сходится при любом выборе начального приближения .

Метод Якоби

Представим матрицу Aв виде суммы трех матриц, где

- нижняя треугольная матрица с 0 на главной диагонали.

- верхняя треугольная матрица с 0 на главной диагонали.

.

Для метода Якоби имеем и:

.

. (3.16)

Запишем метод в координатной форме:

для всех .

для всех .

Предполагается, что для всех.

Алгоритм метода Якоби

• Задание исходных матрицы Aи вектора правой частиf.

• Проверка выполнения условия для всех.

• Задание начального приближения .

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

• Выполнение следующей итерации . Вычисление очередного приближения.

• Проверка условия сходимости. Обычно используют критерий , где- норма.

• В случае выполнения условия - печать решения и невязки, количества выполненных итераций.

Возможные ошибки

• Плохое начальное приближение.

• Ошибки при организации суммирования.

• Замена в формулах известного приближения на искомое.

• Ошибка с индексами переменных.

• Неправильно переписанная формула метода.

• Ошибка в критерии условия сходимости.

Теорема сходимости метода Якоби

Теорема. Пустьс диагональным преобладанием, тогда метод Якоби сходится для любого начального приближения.

Рекомендации

• Если задача не подходит под условие теоремы, то это еще не значит, что метод нельзя использовать.

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

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

Метод Зейделя

Для метода Зейделя берут и:

.

. (3.17)

Запишем метод в координатной форме:

для всех .

Теорема сходимости метода Зейделя

Теорема. Пусть, тогда метод Зейделя сходится для любого начального приближения.

Метод верхней релаксации

Положим и- параметр >0:

.

(3.18)

Запишем метод в координатной форме:

для .

Итак,

.

,

и т.д.

Теорема сходимости метода верхней релаксации

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

Метод итерации

Решаем систему уравнений . Предполагаем, чтодля всех.

Разрешим первое уравнение системы относительно , второе уравнение относительнои т.д. В результате получим следующую систему уравнений:

, (3.19)

где ,приипри.

Следовательно, систему (3.19) можно записать в виде .

Алгоритм метода итерации

• Выбираем начальное приближение .

• Вычисляем ,и т.д.

• Вычисления проводим до тех пор, пока не будет выполнен критерий сходимости итерационного процесса. Например, .

Метод итераций хорошо сходится, если элементы малы по абсолютной величине. Иными словами, матрица системы имеет диагональное преобладание.

Аппроксимация и интерполирование функций

Общие понятия

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

Простейшая задача интерполирования: на отрезке [a,b] задана (n+1) точка, эти точки называются узлами интерполирования, и (n+1) значение функции в этих точках. Требуется построить функцию F(x), принадлежащую известному классу и принимающую в узлах интерполирования те же значения, что и f(x), т.е.

.

Геометрически это означает, что нужно найти кривую некоторого определенного типа, проходящую через систему заданных точек. Это задача становится однозначной, если вместо произвольной функции строить полином P_n(x) степени n такой, что

,

тогда внутри промежутков (x_i, x_i+1) построенный полином будет приближенно описывать функцию f(x).

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