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

.., 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 с.












13