Вычисление погрешности арифметических операций метода простых итерации решение СЛАУ

., w9. Будем искать вектор, минимизирующий функционал невязки Ф (у) на подпространстве W. Для этого рассмотрим следующий итерационный метод.

Положим х° = 0.

Если приближение хk уже найдено, то следующее приближение xk+1 будем искать в виде xk+1 = xk + CkWjk, Ck = const, где

. (36)

Наряду с приближениями xk введем невязки

(37)

Выпишем условия минимума функционала Ф (х'с+1) по Ck. Имеем

(38)

Заметим, что при поиске минимума Ф (х'с+1) достаточно рассматривать только те Wj, для которых, так как в противном случае значение функционала не меняется. Функция, как функция переменной Ck, является многочленом второй степени, причем коэффициент при положителен в силу замечания выше. Отсюда следует, что минимум по Ck при фиксированном j существует и единствен, если. Таким образом, из (38) следует, что Ck удовлетворяет уравнению Откуда При таком выборе Ck

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

1) Вычисляем векторы, и их нормы; в дальнейшем рассматриваем только те векторы, для которых. Не уменьшая общности, будем считать, что число таких векторов равно q.

2) Выбираем на основе априорной информации; в частности, можно взять .

3) Если найден, то и вычисляем по формулам

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

Этап 3 итерационного метода требует, а этап 4 — арифметических операций.

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

Отметим также, что находится в общем случае неоднозначно (таких индексов может быть несколько). В этом случае в качестве можно брать, например, наименьший.

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

Пусть для определенности. Тогда справедлива цепочка неравенств откуда и следует непрерывность рассматриваемого функционала.

Предположим, что утверждение леммы неверно. Тогда существует последовательность такая, что и, где при. Так как в конечномерном пространстве сфера компактна, то существует сходящаяся подпоследовательность. Для простоты изложения предположим, что сходится сама последовательность В силу непрерывности функционала имеем и .

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

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

Доказательство. Так как, то существует постоянная такая, что

Из (34), (35) следует, что невязки удовлетворяют соотношению Положим. Тогда (37) примет вид Поскольку выбиралось из условия минимума, то и мы находимся в условиях предыдущей леммы. Тогда из условий леммы следует оценка Из (34) и (35) имеем откуда, учитывая (36), получаем оценку Применяя к полученному неравенству оценку (38), имеем откуда следует цепочка соотношений Таким образом, последовательность является фундаментальной и имеет предел. В силу построения, минимизирует функционал на подпространстве. Теорема доказана.

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

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

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

Заключение

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

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

Метод решения задачи называется итерационным, если он дает точное решение как предел последовательности приближений, вычисляемых по единообразной схеме, то есть где x — точное решение задачи, x (k) — k-тое приближение (итерация) к решению.

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

Теория получения приближенных решений СЛАУ — часть вычислительной линейной алгебры.

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

Данные теоретические аспекты широко используются не только в математике, но и в программировании.

Список литературы

Волков Е. А. Численные методы: Учеб. пособие для вузов, —

2-е изд., испр. — М.: Наука. Гл. ред. физ.-мат. лит., 1987.

— 248 с.

Исаков, В. Б. Элементы численных методов: Учебное пособие для студентов, обучающихся по специальности Математика группы Педагогические специал. — М.: Академия, 2003.-192 с.

Турчак Л. И., Плотников П. В. Основы численных методов: Учебное пособие. — 2-е изд., перераб. и доп. — М.: ФИЗМАТЛИТ, 2003. — 304 с.