3 = 1
На основе экспериментов со случайными матрицами при различных п убедитесь в выполнении неравенств
^1И11а < |И||е < s/n\\A\\a, а = 1,00
для евклидовой (сферической) нормы (нормы Фробениуса) ЦАЦ#.
Задача 4.2 Напишите программу, реализующую LU-разлоэюепие с выбором главного элемента по строке (схема частичного выбора) с выводом матрицы LU и вектора перенумерации переменных (перестановки столбцов),
который определяет матрицу перестановок Р. С ее помощью найдите LJJ. разлоэюение матрицы Паскаля, для которой
=
i = 1,2.
(i + j-2)1
4i (i-mj-iy.
Проверьте выполнение det(A) = 1 и зависимость определителя от п. По- вторите эксперименты с LU-разлоэюеиием без выбора главного элемента (модуль 1и).
Задача 4.3 Разработайте алгоритм и реализуйте его программно для варианта декомпозиции Холецкого симметричной невыроэюденной матрицы в виде А = LDL*, где L — ниэюняя треугольная матрица с единичной диагональю и D — диагональная матрица, без вычисления квадратного корня. С помощью этой программы найдите декомпозицию Холецкого KMS (К ас- Murdock-Szego) матрицы, для которой
di)=eb~}\ г = 1,2,..., п, j = 1,2,
При различных п и q сравните рассчитанную матрицу D с точным решением, для которого
= < = 1> и \ l-e2, i = 2,3,...,п.
Задача 4.4 Рассмотрите алгоритм построения обратной матрицы на основе решения матричного уравнения
АХ = Е,
где Е —■ единичная, а X — искомая квадратная матрица. Напишите программу вычисления обратной матрицы на основе LU-разлоэ1сение с выбором главного элемента по строке (схема частичного выбора) (задача 4-2). Найдите обратную к матрице Лемера (Lehmer), для которой
г
шт(г, j) тах(г, j) ’
= 1,2, j = 1,2,
При вычислениях с различными значениями п убедитесь в том, что А 1 является трехдиагональной матрицей.
Задача 4.5 Напишите программу для вычисления числа обусловленности квадратной матрицы с использованием норм || • ||„, а = 1,Е,ос (см. задачу 4-1) и вычисления обратной матрицы на основе LU-разлоэюение матрицы (упразднение 4-1). Найдите при различных п число обусловленности матрицы А, в которой
Убедитесь, что обратная матрица является трехдиагональной, внедиаго- иальиые элементы которой а”/±1 = —I, а диагональные —
-1 Г 2, 2 = 1,2, ...,п — 1,
’■* ~ \ 1, г — п.
Задача 4.6 Рассмотрите алгоритм решения системы уравнений с трехдиагональной циклической матрицей, элементы которой ац = 0 при 1 < \i — j\ < п — 1 (а\п Ф О, ani фО), на основе LU-разлоэюения. Покаэюите, что в этом случае
lij ф О, 2 = 1,2, ..., 71 1, j — 2, 2 1, % — 71, j = 1,2, 71,
Uij ф О, j = 1,2 ,...,71 - 1 2 =j,j - 1, j =71, i = 1,2,n,
и напишите программу решения задачи Ах = f. Найдите решение уравнения с циклической трехдиагональной матрицей, для которой
ац 2 ~Ь h , 1, а\п — апi = 1
при правой части
fi = ^1 + ^ sin2(7r/i)^ sin(27r(2 - l)/l), 2 = 1,2, ..., 71
где h = 7i~1. Покажите, что
yi = sin(27r(2 - 1 )h), 2 = 1,2,..., n
есть 7почное решение рассматриваемой задачи.
Итерационные методы линейной алгебры
Для приближенного решения больших систем линейных алгебраических уравнений используются итерационные методы. Такие системы возникают при приближенном решении многомерных краевых задач математической физики. Рассмотрение начинается с классических итерационных методов Якоби и Зейделя. Приведены базовые понятия теории итерационных методов решения систем линейных уравнений, рассматриваемых в евклидовых пространствах. Обсуждаются проблемы выбора итерационных параметров, матрицы перехода (переобуславливателя).
Основные обозначения
|
Х= {Xi} = {хих2,...,хп}
|
— n-мерный вектор
|
А = {<2ц }
|
— матрица с элементами
|
Е
|
— единичная матрица
|
D = diag {dud2,...,dn}
|
— диагональная матрица
|
ы
|
— норма вектора х
|
1И11
|
— норма матрицы А
|
хк
|
— приближенное решение на к-й итерации
|
zk = Xк - X
|
— погрешность приближенного решения
|
?г
II
?г
1
|
— невязка на к-й итерации
|
Т,тк
|
— итерационные параметры
|
Итерационное решение систем линейных уравнений
Рассматриваются проблемы итерационного решения системы линейных уран- нений
Ах = f (5.1)
для нахождения вектора х. В теории итерационных методов матрица А обычно рассматривается как линейный оператор, действующий на евклидовом
пространстве Н = /2, в котором скалярное произведение есть (х,у) = У^ж^,
г=1
а норма \\х\\ = (ж,ж)1/2.
Итерационный метод основан на том, что начиная с некоторого начального приближения х° 6 Н последовательно определяются приближенные решения уравнения (5.1) ж1, ж2,..., хк,..., где к — номер итерации. Значения xk+l определяются по ранее найденным хк, ж*-1,..,. Если при вычислении хк+1 используются только значения на предыдущей итерации хк, то итерационный метод называется одношаговым (двухслойным). Соответственно, при использовании хк и хк~г итерационный метод называется двухшаговым (трехслойным).
Двухслойный итерационный метод записывается в следующей канонической форме
хк+1 _ „к
В— 1-Axk = f, к = 0,1,— (5.2)
тк+1
Для характеристики точности приближенного решения естественно ввести погрешность zk = хк — х. Будем рассматривать сходимость итерационного метода в энергетическом пространстве Hr, порожденном симметричной и положительно определенной матрицей R. В HR скалярное произведение и норма есть
(v,w)r = (Ry,w), |М|я = ((у,2/)я)1/2-
Итерационный метод сходится в Hr, если \\zk\\R —► 0 при к —> оо. В качестве меры сходимости итераций принимают относительную погрешность е, так что на К-й итерации
||я* -х||я < £||ж° -а;||я. (5.3)
В силу того, что само точное решение х неизвестно, оценка точности приближенного решения проводится по невязке
rk = Axk-f = Ахк - Ах,
которая может быть вычислена непосредственно. Например, итерационный процесс проводится до выполнения оценки
1|г*||<ф°||. (5.4)
Использование критерия сходимости (5.4) соответствует выбору R = А*А в (5.3). Минимальное число итераций, которое гарантирует точность е (выполнение (5.3) или (5.4)), обозначим К(е).
При построении итерационного метода мы должны стремиться к минимизации вычислительной работы по нахождению приближенного решения задачи (5.1) с заданной точностью. Пусть Qk — число арифметических действий для
нахождения приближения хк и пусть делается К > К(е) итераций. Тогда о(у. щие затраты оцениваются величиной
Do'stlaringiz bilan baham: |