Федченко Г.М. Лекции. Численные методы
Подождите немного. Документ загружается.
РЕШЕНИЕ СЛАУ. ПРЯМЫЕ МЕТОДЫ (ПРОДОЛЖЕНИЕ)
A – вырожденная, если для некоторых b решение системы Ax=b не
существует, а для других b оно будет не единственным. Если матрица A –
почти вырожденная, то можно ожидать, что малые изменения A и b вызовут
очень большие изменения в x.
Умножение x на матрицу A приводит к вектору Ax, норма которого
может сильно отличаться от |||x||. Это изменение нормы прямо связано с
чувствительностью матрицы.
||Ax|| M∙||x||
m∙||x|| ||Ax||
Отношение M/m и называют числом обусловленности матрицы A:
, (6.10)
обозначение cond от английского слова conditioned – обусловленный.
Но max;\s\do11(x№0 – норма, согласованная с нормой x.
Обозначим образ оператора Ax за y: y=Ax. Тогда x=A
–1
y. При x0, y0.
.
Таким образом:
cond(A)= |||A||∙||A
–1
||. (6.11)
Покажем, что cond(A) измеряет чувствительность к погрешностям.
Пусть правая часть уравнения Ax=b получила приращение («возмущение»)
b, т.е. вместо истинного вектора b используется приближенный вектор b.
Реакцией решения x на возмущение b правой части будет вектор поправок
x, т.е. x+x – решение уравнения
A(x+x)=b+b.
Так как Ax=b, Ax=b, откуда x= A
–1
b. Нормируем равенства и
воспользуемся свойством нормы:
||b|| = ||Ax|| ||A||∙||x||,
||x|| = ||A
–1
b|| || A
–1
||∙||b||,
где матричная норма согласована с векторной нормой. Перемножим два
неравенства одинакового смысла:
||b||∙||x|| ||A||∙||x||∙|| A
–1
||∙||b||,
откуда
, т.е.
. (6.12)
Легко показать, что то же самое число cond(A) служит
коэффициентом роста относительных погрешностей при неточном задании
элементов матрицы A. А именно, если матрица A получила возмущение A и
x+x – решение возмущенной системы
(A+A)(x+x)=b,
то справедливы неравенства
и . (6.13)
59
РЕШЕНИЕ СЛАУ. ПРЯМЫЕ МЕТОДЫ (ПРОДОЛЖЕНИЕ)
С более точным соотношением зависимости относительной
погрешности решения
x
от относительных погрешностей
A
и
b
одновременно можно познакомиться в учебнике В.М.Вержбицкого «Основы
численных методов», с.p30.
Основные свойства числа обусловленности:
1. Так как M ≥ m, cond(A) ≥ 1.
2. Умножение матрицы A на число не меняет числа обусловленности:
cond(с∙A) = cond(A).
3. Если D – диагональная матрица, то
.
Если мы рассмотрим матрицу
,
то cond(A) = 1 и матрица идеально обусловлена, в то время как det(A) = 10
–100
.
Таким образом, этот пример демонстрирует, что малость определителя
матрицы A является необходимым, но не достаточным условием плохой
обусловленности системы.
Число обусловленности играет фундаментальную роль в анализе
ошибок округления, совершаемых в ходе гауссова исключения. Пусть A и b
заданы точно, x
*
– приближенное решение, полученное методом Гаусса в
арифметике с плавающей точкой. Тогда
и , где c – обычно немного больше 1.
Основной результат в исследовании ошибок округления в гауссовом
исключении принадлежит Дж.Х.Уилкинсону. Он доказал, что вычисленное
решение x
*
точно удовлетворяет системе
(A+A)x
*
= b,
где A – матрица, элементы которой имеют величину порядка ошибок
округления в элементах матрица A. Тем самым все ошибки округления
могут быть слиты воедино и рассматриваться как единственное возмущение,
внесенное в матрицу A в момент записи в память компьютера, само же
исключение осуществляется без ошибок. В этом смысле метод Гаусса –
лучший алгоритм решения СЛАУ. Контроль качества вычислений может
быть осуществлен по вектору невязок только для хорошо обусловленных
систем.
Вычисление и оценивание cond(A):
cond(A) = ||A||∙||A
–1
||
60
РЕШЕНИЕ СЛАУ. ПРЯМЫЕ МЕТОДЫ (ПРОДОЛЖЕНИЕ)
Можно получить нижнюю оценку числа обусловленности через собственные
числа матрицы A, так как любая норма матрицы не меньше модуля
максимального собственного числа этой матрицы:
||A|| ≥ |λ
max
|.
Так как собственные числа матрицы A
–1
обратны собственным числам
матрицы A (, где λ
i
– собственные числа матрицы A), то
,
– нижняя оценка cond(A).
Пример 6.1.
, .
1 способ: ||A||
= 1101, ||A
–1
||
=1011.
cond(A) = 1101∙ 1011=1113111>10
6
.
2 способ: . Решим уравнение | A–λE| = 0:
λ
2
–1002λ+1 = 0
λ
1
1002, λ
2
0.000998
Можно оценить число обусловленности матрицы A путем проведения
вычислительного эксперимента. Рассматривая в качестве решения вектор и
подставляя его компоненты в левую часть системы найдем вектор правых
частей уравнения , где , i=1,2,…,n. Таким образом, x является точным
решением системы Ax=с. Проведя вычислительный эксперимент, гауссово
исключение в конечноразрядной арифметике с машинным эпсилон
1
,
получим приближенное решение x; \s\up6((и оценим его относительную
погрешность по норме-максимум:
.
Имея эту оценку, можно определить приближенное значение cond(A).
6.5. Контрольные вопросы и упражнения
1. Подсчитайте количество операций типа умножения, необходимых для
вычисления СЛАУ методом квадратных корней.
2. Подсчитайте количество арифметических операций, необходимых для
решения системы линейных уравнений с трехдиагональной матрицей
61
РЕШЕНИЕ СЛАУ. ПРЯМЫЕ МЕТОДЫ (ПРОДОЛЖЕНИЕ)
коэффициентов методом прогонки и оцените время, затрачиваемое
компьютером для решения системы 100, 1000 уравнений.
3. Подсчитайте количество арифметических операций, необходимых для
вычисления поправки приближенного решения.
4. Модифицируйте алгоритм метода Гаусса, разделив его на блоки
прямого и обратного хода с тем, чтобы можно было с их помощью
получать решение системы с любой правой частью.
5. Вывести соотношения (6.13).
62
РЕШЕНИЕ СЛАУ. ИТЕРАЦИОННЫЕ МЕТОДЫ
Лекция 7
РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ.
ИТЕРАЦИОННЫЕ МЕТОДЫ
7.1. Введение
Точные методы решения линейных систем применяют для решения
линейных систем относительно небольшой размерности (до 10). Для решения
систем большей размерности (10–10) используют итерационные методы.
Итерационные методы хороши для систем с разреженными матрицами.
Разреженными называют матрицы, большинство элементов которых нули.
В итерационных методах предполагается осуществление следующих
трех этапов:
1. построение последовательных приближений итерационного
процесса, сходящегося к точному решению (т.е. построение
последовательности векторов , , …, , сходящейся к точному решению ;
2. определение критерия сходимости этого процесса,
позволяющего определить момент достижения требуемой точности;
3. исследование скорости сходимости и оптимизация
итерационного процесса с целью уменьшения числа операций,
необходимых для достижения требуемой точности.
Итерационные методы позволяют получить решение с наперед
заданной точностью, если доказана сходимость процесса. Строго точного
решения итерационные методы не дают, поскольку оно достигается как
предел последовательности векторов.
Рассмотрим несколько итерационных методов решения СЛАУ.
7.2. Метод простой итерации
В методе простой итерации СЛАУ
Ax = b (7.1)
тем или иным способом приводится к эквивалентной системе вида
x = Cx+d. (7.2)
Систему можно трактовать как задачу о неподвижной точке линейного
отображения F: xCx+d в пространстве . Задав начальное приближение для
вектора решения, строится последовательность с помощью рекуррентного
соотношения
= C+d, k=1, 2, … (7.3)
63
РЕШЕНИЕ СЛАУ. ИТЕРАЦИОННЫЕ МЕТОДЫ
Если отображение F является сжимающим
1
, то последовательность
сходится и ее предел является решением системы (7.2), а значит и исходной
системы (7.1).
Упражнение. Покажите, что пределом сходящейся итерационной
последовательности, построенной с помощью рекуррентного соотношения
(7.3) является корень уравнения (7.2).
Эквивалентных преобразований, приводящих систему вида Ax = b к
виду x = Cx+d бесчисленное множество. Например: Ax = b x+Ax = x+b x
= x–Ax +b, т.е. x = (E–A)x +b.
Пример 7.1. Пусть задана система уравнений вида Ax = b:
.
Вычленим единицы из диагональных элементов, в результате чего система
преобразуется к виду:
,
к виду x = Cx+d, где
, .
Выберем в качестве начального приближения к корню нулевой вектор: ,
тогда
Скорее всего, вычисление последующих векторов итерационной
последовательности продемонстрирует нам сходимость к корню . Проверьте.
Погрешность найденного третьего приближения оценим по норме-максимум:
.
При реализации итерационных методов приходится решать комплекс
вопросов о сходимости итерационного процесса:
1) какими свойствами должна обладать матрица C, вектора d и x
(0)
,
чтобы последовательность при k имела пределом x* – неподвижную
точку отображения F, и значит решение уравнения Ax = b;
2) с какой скоростью сходится этот процесс;
3) сколько нужно сделать итераций, чтобы при заданном
начальном приближении x
(0)
найти решение задачи с заданной
точностью?
Теорема 7.1. (необходимое и достаточное условие сходимости метода
простых итераций) Необходимым и достаточным условием сходимости
1
q, 0<q<1, что для x
1
, x
2
R
n
: (Fx
1
, Fx
2
) q∙(x
1
, x
2
).
64
РЕШЕНИЕ СЛАУ. ИТЕРАЦИОННЫЕ МЕТОДЫ
метода простых итераций при любом начальном приближении к решению
системы (7.2) является требование, чтобы все собственные числа матрицы C
были по модулю меньше 1.
На практике этим условием трудно воспользоваться, так как найти
собственные значения обычно сложнее, чем решить линейную систему.
Достаточное условие сходимости метода простой итерации определяется
следующей теоремой.
Теорема 7.2. (достаточное условие сходимости метода простых итераций)
Если какая-либо норма матрицы C, согласованная с нормой вектора x,
меньше единицы (||C||<1), то последовательность в методе простой итерации
сходится к точному решению со скоростью, не меньшей скорости
геометрической прогрессии со знаменателем q, ||C||q<1, при любом
начальном приближении .
Обозначим через =– – погрешность, получаемую на k-ом шаге
итерационного процесса. Вычтем из соотношения =C+d равенство (7.3) и
получим =C. Переходя к нормам и используя условие согласованности норм,
имеем
|||| = |||| ||||·|||| ||C||·||||.
Если ||C||<1, то при любом векторе начальной погрешности, т.е. при любом
начальном векторе , норма погрешности ||||0 не медленнее геометрической
погрешности со знаменателем q.
Замечание. Условие теоремы 7.2, ||C||<1, является достаточным, но не
необходимым. Его выполнение гарантирует сходимость метода, но
невыполнение в общем случае не означает, что метод простой итерации
расходится.
7.3. Метод Якоби
Простейшим и распространенным способом приведения системы
Ax=b к виду (7.2) является выделение диагональных элементов, при этом
каждое i-ое уравнение разрешается относительно i-ого неизвестного:
, i=1, 2, …, n, (7.4)
и рекуррентное соотношение метода простой итерации запишется в виде
, i=1, 2, …, n; k=1, 2, … (7.5)
Данное преобразование и организация итерационного процесса
называются методом Якоби.
65
РЕШЕНИЕ СЛАУ. ИТЕРАЦИОННЫЕ МЕТОДЫ
Матрица итерирования C при этом имеет вид
, а вектор .
Представим метод Якоби в матричном виде. Для этого запишем
матрицу A в виде
A=L+D+R,
где D – диагональная, а L и R – соответственно левая и правая строго
треугольные. Тогда система (7.1) может быть записана в виде
Lx+Dx+Rx=b,
и если на диагонали исходной матрицы нет нулей, то
x = – D
–1
(L+R)x+ D
–1
b,
т.е. в равенстве (7.2) следует положить
C = – D
–1
(L+R), d = D
–1
b.
Таким образом, в векторно-матричных обозначениях формулы для
построения итерационной последовательности метода Якоби имеют вид
x
(k)
= – D
–1
(L+R)x
(k–1)
+ D
–1
b, k=1, 2, … .
Для метода Якоби достаточное условие сходимости итерационного
процесса может быть сформулировано как условие преобладания
диагональных элементов матрицы A, т.е.
, i=1, 2, …, n;
или
, j=1, 2, …, n.
Теорема 7.3. (достаточное условие сходимости метода Якоби) В случае
диагонального преобладания в матрице A системы (7.1) метод Якоби
сходится.
Теорема 7.4. (необходимое и достаточное условие сходимости метода Якоби)
Метод Якоби сходится к решению системы (7.1) в том и только том случае,
когда все корни уравнения
по модулю меньше 1.
Перейдем к вопросу об оценке погрешности решения.
7.4. Оценка погрешности и критерий окончания итерационного
процесса
Теорема 7.5. Если какая-либо норма матрицы C, согласованная с нормой
вектора x, меньше единицы (||C||q<1), то имеют место следующие оценки
погрешности приближений, полученных по методу простой итерации:
, (7.6)
66
РЕШЕНИЕ СЛАУ. ИТЕРАЦИОННЫЕ МЕТОДЫ
, (7.7)
Оценку (7.6) называют апостериорной («a posteriori» – из опыта), оценку
(7.7) – априорной («a priori» – до опыта), т.к. априорной оценкой можно
воспользоваться до начала счета, а апостериорной – лишь после проведения
k-ой итерации.
Запишем разность между точным решением = C+d и k-ым приближением
= C+d
–=C–C=C(–).
Прибавим и отнимем в правой части C, в результате получим
–=C(–)+C(–).
Переходя к нормам и используя условие согласованности норм, имеем
||–||=||C(–)+C(–)||||C||·||–||+||C||·||–||
q·||–||+ q·||–||.
Учитывая, что 1– q>0, получаем
.
Так как ===…=, то
.
Замечание 1. Также можно получить другую оценку погрешности k-ого
приближения метода простой итерации:
. (7.8)
Замечание 2. Погрешности последовательных итераций связаны
соотношением
,
т.е. погрешность изменяется на шаге линейно. Таким образом, метод имеет
линейную сходимость или, другими словами, первый порядок сходимости.
Вместе с тем количество итераций, необходимое для достижения требуемой
точности, зависит от значения q и начального приближения .
Замечание 3. Оценки (7.7) и (7.8) позволяют подсчитать число итераций k,
достаточных для получения решения с заданной точностью
(в смысле
допустимого уровня абсолютных погрешностей) при выбранном начальном
векторе . Для этого нужно найти наименьшее целое решение неравенства
,
или неравенства
.
67
РЕШЕНИЕ СЛАУ. ИТЕРАЦИОННЫЕ МЕТОДЫ
Замечание 4. Оценкой (7.6) удобно пользоваться в процессе вычислений и
останавливать итерационный процесс, как только выполнится неравенство
.
В случае же q гарантией достижения точности
будет неравенство
.
Замечание 5 (о выборе начального приближения). Выполнения достаточного
условия гарантирует сходимость метода простой итерации при любом
начальном векторе . Итераций потребуется тем меньше, чем ближе к . Если
нет никакой дополнительной информации о решении задачи (например,
решение близкой задачи или грубое решение исходной задачи), то за обычно
принимается вектор d свободных членов системы (7.2). Мотивация этого
может быть такой: матрица C «мала», значит вектор Cx «мал»,
следовательно, и вектор не должен сильно отличаться от вектора d. При
выборе =d оценка (7.7) примет вид
.
7.5. Метод Зейделя
Под методом Зейделя понимается такое видоизменение метода
простой итерации, при котором для подсчета i-ой компоненты на k-ом шаге
используются уже найденные на этом шаге новые значения первых i–1
компонент. Это означает, что если система (7.1) тем или иным способом
сведена к виду (7.2) x = Cx+d, то приближения к ее решению по методу
Зейделя определяются формулами
,
где k=1, 2, …, а – начальное приближение. т.е.
i
n
ij
k
jij
i
j
k
jij
k
i
dxcxcx
1
1
1
для i=1, …, n.
Применительно к компьютерным расчетам один полный, т.е.
векторный шаг метода Зейделя может интерпретироваться как реализация
формулы (7.2), где под знаком равенства понимается знак присваивания, а
под x – один и тот же линейный массив из n элементов, на начальном шаге
заполненный компонентами вектора , на остальных шагах постепенно
обновляемый новыми компонентами.
При компьютерной реализации метода простой итерации на каждом
шаге необходимо сохранять целиком n-мерный массив очередного
приближения, подставляемый в правую часть до тех пор, пока не
сформируется новое итерационное приближение. В связи с такой
интерпретацией метод Зейделя называют методом последовательных
смещений, а метод простой итерации – методом одновременных смещений.
68