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

Введение
1Краткое описание метода простых итераций решения СЛАУ и вычисление погрешности арифметических операций метода простых итераций решения СЛАУ
1.1Сущность метода простых итераций решения СЛАУ
1.2Методика вычисления погрешности операций метода простых итераций решения СЛАУ
2Погрешность приближенного решения системы линейных уравнений
2.1Постановка проблемы
2.2Погрешность при использовании метода простых итераций
Заключение
Список литературы

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

Для относительных погрешностей произведения и частного приближенных чисел верны оценки:
если
и ,
то   , .
Предположим, что матрица системы линейных уравнений и вектор правых частей заданы неточно и вместо предъявленной к решению системы
(19)
в действительности решается некоторая система
, где  (20)
Обозначим решения (19) и (20) через  и 
Оценим погрешность решения .
Подставим выражения ,  и  в (20)
Вычитая (20), получим
(21)
Если малы  и , то следует ожидать и малости . Тогда слагаемое  имеет более высокий порядок малости.
Отсюда следует оценка погрешности
. (22)
Довольно распространен случай, когда погрешность матрицы системы существенно меньше погрешности правой части; в качестве модели этой ситуации будем рассматривать случай точного задания матрицы системы. Тогда, полагая  в (33) имеем
(23)
Для качественной характеристики связи между погрешностями правой части и решения вводится понятие обусловленности матрицы системы. Абсолютные погрешности правой части и решения системы зависят от масштабов, которыми измеряется эти величины и матрица системы. Поэтому правильнее характеризовать свойства системы через связь между относительными погрешностями правой части и решения.
Для относительной погрешности решения из (34) имеем
(24)
отсюда .
Подставляя оценку для  в (24) имеем
(25)
Величину  называют мерой обусловленности матрицы.
Величина относительной погрешности решения при фиксированной величине относительной погрешности правой части может стать сколь угодно большой при достаточно большой мере обусловленности матрицы. Число обусловленности зависит от выбора нормы матрицы. Любая норма матрицы не меньше ее наибольшего по модулю собственного значения, т. е. . Собственные значения матрицы  и  взаимно обратны; поэтому .
Таким образом,
(26)
Системы уравнений и матрицы с большими значениями мер обусловленности принято называть плохо обусловленными, а с малыми - хорошо обусловленными.
2 Погрешность приближенного решения системы линейных уравнений
2.1 Постановка проблемы
Предположим, что матрица и правая часть системы заданы неточно и вместо предъявленной к решению системы
(27)
в действительности должна была решаться некоторая система
. (28)
Пусть известны оценки и . Займемся оценкой погрешности ре­шения.
Сначала выделим главный член погрешности. Будем обозначать ре­шения (27) и (28) через X и X* и разность X* - X — через r. Подставив выражения и X* в (28), будем иметь
Вычитая из этого равенства (27), получим
Откуда
и
. (29)
Если и малы, то следует ожидать и малости ||r||. Тогда слагае­мое Аr имеет более высокий порядок малости; отбрасывая это слагаемое, получаем
Отсюда следует оценка погрешности
. (30)
Строгая оценка погрешности получается следующим образом. Вслед­ствие (29) выполняется неравенство
Предположим, что < 1. Перенеся последнее слагаемое в левую часть и поделив неравенство на коэффициент при ||r||, получим оценку
(31)
Довольно распространен случай, когда погрешность матрицы системы существенно меньше погрешности правой части. В качестве модели этой ситуации будем рассматривать случай точного задания матрицы системы. Тогда, полагая в (31) = 0, имеем
Для качественной характеристики связи между погрешностями правой части и решения вводятся понятия обусловленности системы и обусло­вленности матрицы системы. Абсолютные погрешности правой части и решения системы зависят от масштабов, которыми измеряются коэффи­циенты системы. Поэтому удобнее характеризовать свойства системы че­рез связь между относительными погрешностями правой части и реше­ния.
Соответственно этому в качестве меры обусловленности системы при­нимается число
Отсюда получаем оценку относительной погрешности решения через меру обусловленности системы и относительную погрешность правой части:
(32)
Так как то
Иногда удобнее иметь более грубую характеристику свойств системы только через свойства матрицы А. Эту характеристику называют мерой (или числом) обусловленности матрицы А. Согласно это­му определению и (31), имеем оценку
связывающую относительные погрешности правой части и решения толь­ко через свойства матрицы системы. Так как
то
Поскольку любая норма матрицы не меньше ее наибольшего по модулю собственного значения, то поскольку собственные значе­ния матриц А и А-1 взаимно обратны, то
Таким образом,
В частности, при А = Ат имеем и
Следовательно, в случае нормы || • ||2
Рассмотрим вопрос о погрешности решения вследствие округления в ЭВМ правой части. Пусть, как обычно, t — двоичная разрядность чисел в ЭВМ. Каждый элемент bi правой части округляется с относительной погрешностью , т.е. с абсолютной погрешностью, равной 0(\Ы\2~1), поэтому
Следовательно,
.
При практической работе вопрос: о строгой оценке погрешности полу­ченного приближенного решения системы линейных уравнений с помо­щью полученных неравенств или каким-либо иным способом возникает редко. Однако информация о порядке погрешности решения часто по­лезна для получения качественных выводов о том, с какой точностью разумно решать задачу. Соотношения (30), (31) оценивают сверху погреш­ность решения, являющуюся следствием погрешности исходных данных. Из равенства (29) видно, что оценки (30), (31) довольно точны, поэтому обычно не имеет смысла стремиться получать решение задачи с погреш­ностью, существенно меньшей чем а.
Системы уравнений и матрицы с большими значениями мер обусло­вленности принято называть плохо обусловленными, а с малыми — хоро­шо обусловленными. Если правая часть (4), оценивающая погрешность решения через погрешность исходных данных, или оценка вычислитель­ной погрешности недопустимо велики, то полезно принять во внимание какую-то дополнительную информацию о решении рассматриваемой за­дачи. Подход к решению такой задачи должен быть таким же, как в случае некорректных задач.
2.2 Погрешность при использовании метода простых итераций
Будем решать систему уравнений методом простых итераций.
при некотором начальном приближении х°. Пусть
Приравнивая коэффициенты при е./, получим соотношения
Последовательно выражая каждое через предыдущие, имеем
Если , то при
поэтому
Пусть , т.е. относительно мало. При больших значениях величина быстро стремится к нулю с ростом п и близко к своему предельному значению . В то же время иногда удается подобрать начальное приближение, для которого величины относительно малы при малых . Тогда при небольшом п коэффициенты , соответствующие таким , еще не будут недопустимо большими и получаемое приближение может оказаться приемлемым.
В других случаях решение задачи находят, минимизируя некоторый функционал, близкий к, например функционал с малым а > 0.
Успешность применения описанных приемов в случае несимметричных матриц А в существенной степени зависит от структуры жордановой формы и от ряда свойств матрицы. Здесь часто решение находят, ми­нимизируя функционал
при малых а > 0; значение а опять-таки подбирается экспериментально из сравнения результатов расчетов при различных а.
Другая группа методов основана на представлении матрицы системы А в виде
А = GP,
где G и Р— ортогональные матрицы, а А — двухдиагональная матрица, у которой могут быть отличными от нуля элементы при j = i и j=i+1
Большинство из описанных методов решения систем уравнений с пло­хо обусловленной матрицей относится к методам регуляризации.
Рассмотрим еще один метод решения плохо обусловленных систем ли­нейных алгебраических уравнений. Пусть
. (33)
Относительно А будем считать, что в спектре матрицы А*А есть как собственные числа порядка 1, так и собственные числа, близкие (или даже равные) к нулю. Это как раз и означает, что матрица А плохо обусловлена.
Заметим, что в силу наших предположений относительно собственных значений матрицы А*А, часть из них может быть равна нулю. Таким образом, уравнение (33), вообще говоря, может не иметь решения в клас­сическом смысле.
Назовем решением X уравнения (33) вектор, который минимизирует функционал невязки, а именно,
(34)
здесь и далее в под нормой мы будем понимать ев­клидову норму вектора. Выписывая уравнение Эйлера для функционала , мы получим
. (35)
Уравнение (35), в отличие от (33), всегда имеет решение. Действитель­но, непосредственной проверкой убеждаемся, что ker A*A = ker А Необ­ходимым и достаточным условием существования решения линейной си­стемы уравнений (35) является ортогональность правой части ядру ма­трицы системы, т.е. вектор А*b должен быть ортогонален ядру ker А* А, которое, как мы отметили выше, совпадает с ядром ker А Но из вида правой части видно, что она действительно ортогональна ядру А. Та­ким образом, система (35) всегда имеет решение. В общем случае таких решений может быть несколько.
Описываемый ниже метод заключается в минимизации функционала Ф(у) методом оптимального покоординатного спуска; на каждом шаге выбирается координата, спуск по которой будет оптимальным в смысле минимизации Ф(у). В качестве координатных (базисных) векторов можно выбрать любую ортонормированную систему.
Пусть wi,..., wq — ортонормированная система векторов в Rm (не обязательно базис) и по крайней мере для одного из векто­ров. Обозначим через W линейную оболочку векторов wi,..., w9. Будем искать вектор, минимизирующий функционал невязки Ф(у) на подпро­странстве W. Для этого рассмотрим следующий итерационный метод.
Положим
х° = 0.
Если приближение хk уже найдено, то следующее приближение xk+1 бу­дем искать в виде xk+1 = xk + CkWjk, Ck = const, где
. (36)
Наряду с приближениями xk введем невязки
(37)
Выпишем условия минимума функционала Ф(х'с+1) по Ck. Имеем