main (1160440), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Значит, в целом3для обращения матрицы необходимо 3 + 3− ∼ 34 3 операций. Покажем теперь, чтоэто число операций можно уменьшить. Рассмотрим систему уравнений (5):11 1 = 0()⇒1 = 0,()()⇒2 = 0,()()⇒3 = 0,21 1 + 22 2 = 0()31 1 + 32 2 + 33 3 = 0()()()...()()()⇒ −1 = 0.−1,1 1 + . . . + −1,−1 −1 = 0()= 1. Предполагая, что ̸= 0, получим:Рассмотрим -ое уравнение: ()=1.(7)Запишем уравнения системы при > ()()() + ,+1 +1 + .

. . + = 0, = ( + 1), ,(8)()и выразим из них :−()−1∑︀=() , = ( + 1), .(9)Перейдем к подсчету числа операций, необходимых для решения систем уравнений (5) и (6).При фиксированных и в формуле (9) получаем ( − ) умножений и одно деление ив уравнении (7) одно деление. Варьируя индекс от 1 до , при фиксированном получаем=( − )( − + 1)2умножений и (− +1) делений. Таким образом, число действий, необходимое для решенияодной системы (5) равно( − ) + ( − − 1) + . . . + 1 =( − )( − + 1) 2( − + 1)( − + 1)( − + 2)+=.222Общее число действий, необходимое для решения всех систем (5) равно∑︁( − + 1)( − + 2)2=1Задача.

Показать, что сумма (10) равна.(10)(+1)(+2).6Решение. Сделаем замену = − + 1 в формуле (10):∑︁( − + 1)( − + 2)=12=∑︁( + 1)=12.Преобразовав полученное выражение, получим искомый результат:(︃ )︃(︂)︂1 ∑︁ 2 ∑︁1 ( + 1)(2 + 1) ( + 1)( + 1)( + 2) + =+=.22626=1=1§4. Метод квадратного корня152.Аналогично получаем, что число операций для решения всех систем вида (6) равно (−1)2Просуммируем число операций для факторизации исходной матрицы и для решения систем (5) и (6) при = 1, :3 − ( + 1)( + 2) 2 ( − 1)++= 3 .362Описанный выше метод обращения произвольной невырожденной матрицы называетсяметодом Гаусса-Жордана.

Отметим, что он является самым эффективным методом обращения невырожденных матриц произвольного вида.§4Метод квадратного корняОпределение. Квадратная матрица называется эрмитовой (самосопряженной), если = * (ее элементы связаны соотношением = ).Рассмотрим задачу = ,(1)где ∈ C× , = * , || ≠ 0, = (1 , 2 , . . . , ) , = (1 , 2 , . . . , ) , и одиниз прямых методов ее решения — метод квадратного корня (метод Холецкого).Заметим, что хотя класс эрмитовых матриц с точки зрения линейной алгебры достаточно узок, на практике часто возникают модели, описываемые именно этим классом матриц.Поэтому с практической точки зрения такое ограничение на систему (1) вполне допустимо.Факторизуем эрмитову матрицу в виде = * ,(2)где матрица — верхнетреугольная матрица с положительными элементами на главнойдиагонали, а — диагональная матрица со значениями ±1 на главной диагонали:⎛⎞⎛⎞11 12 · · · 111 0 · · ·0⎜ 0 22 · · · 2 ⎟⎜ 0 22 · · ·0 ⎟⎜⎟⎜⎟=⎜ .,>0,=⎟⎜..

. ......... ⎟ , = ±1...⎝ ..⎠⎝....... ⎠00· · · 00· · · Покажем, что факторизация (2) возможна на примере вещественной симметрическойматрицы второго порядка:(︂)︂11 12== , 12 = 21 .21 22Матрицы и будем искать в виде(︂)︂11 12=, > 0, = 1, 2,0 22(︂)︂11 0 = =,12 22(︂)︂11 0=, = ±1, = 1, 2.0 22*16Глава 1. Численные методы линейной алгебрыНайдем матрицу :(︂ =11 00 22)︂ (︂)︂(︂)︂11 1211 11 11 12=.0 22022 22Домножим матрицу слева на :(︂)︂ (︂)︂(︂11 011 11 11 1211 211 ==12 22022 2211 11 12)︂11 11 12.11 212 + 22 222Приравняем элементы матриц и :⎧2⎪⎨ 11 = 11 1112 = 11 11 12⎪⎩22 = 11 212 + 22 222 .(3)(4)(5)Из неравенства 11 > 0 и из уравнения (3) следует, что√︀11 = sgn 11 , 11 = |11 |.Рассмотрим уравнение (4).

Заметим, что 11 11 ̸= 0, и получим12 =12.11 11Наконец, рассмотрим уравнение (5). Получим соотношение 222 22 = 22 − 11 212 , праваячасть которого известна. Следовательно,√︁22 = sgn(22 − 212 11 ), 22 = |22 − 212 11 |.Таким образом, вещественную симметрическую матрицу второго порядка можно факторизовать в виде (2).Рассмотрим теперь произвольную эрмитову матрицу ( × ). Запишем уравнениедля элементов матрицы :() =∑︁ ,, = 1, .=1Учитывая диагональную структуру матрицы , получим:() = .Домножим матрицу слева на * : = ( * ) =∑︁( * ) ,, = 1, .=1Выделим -ое слагаемое из последней суммы и учтем, что ( * ) = : =−1∑︁=1 + +∑︁=+1 ,, = 1, .§4.

Метод квадратного корня17Третье слагаемое из равенства равно нулю в силу того, что матрица * является нижнетреугольной: = 0, > . Тогда получим: =−1∑︁ + ,, = 1, .(6)=1Так как матрица эрмитова, можем рассматривать это равенство только в случае 6 .При = получим:−1∑︁ = + , = 1, .=1Учтем, что = | |2 : =−1∑︁ | |2 + | |2 , = 1, ,=1 | |2 = −−1∑︁| |2 , = 1, .| |2 ), = 1, ,(7)⎯⃒⃒⎸⃒−1⃒∑︁⎸⃒⃒| |2 ⃒, = ⎷⃒ −⃒⃒ = 1, .(8)=1Выразим и : = sgn( −−1∑︁=1=1Рассмотрим случай ̸= ( < ). В уравнении (6) выделим второе слагаемое: = −−1∑︁ ,, = 1, .=1В силу того, что — вещественные положительные числа, получим = −−1∑︁ ,, = 1, .=1Так как ̸= 0, то получим выражения для коэффициентов : − =−1∑︀ =1 ,, = 1, , < .(9)Таким образом, для вычисления элементов матриц в разложении (2) были получены явныеформулы (7) – (9).Метод квадратного корня позволяет примерно вдвое уменьшить количество операций,3необходимых для решения системы (1), по сравнению с методом Гаусса — до ∼ 6 умножений и делений и операций извлечения квадратного корня.

Однако, метод справедливтолько в случае, если матрица системы линейных уравнений эрмитова.18§5Глава 1. Численные методы линейной алгебрыПримеры и канонический вид итерационных методов решения СЛАУРассмотрим матричное уравнение = ,(1)где || ≠ 0, ( × ), = (1 , 2 , .

. . , ) , = (1 , 2 , . . . , ) .Распишем систему (1) покоординатно:∑︁ = , = 1, .(2)=1Выделим -ое слагаемое в сумме:−1∑︁∑︁ + +=1 = , = 1, .=+1Предположим, что элементы главной диагонали матрицы отличны от нуля: ̸= 0, =1, . Тогда уравнение (2) разрешимо относительно : −−1∑︀=1 =∑︀ − =+1, = 1, .Все итерационные методы основаны на построении последовательности векторов =(1 , .

. . , ) такой, что → при → ∞, где — точное решение матричного уравнения (1). Вектор называется -ой итерацией метода.Отметим, что при выборе итерационного метода важно, чтобы метод был легко реализуем и сходился к решению достаточно быстро.Определение.

Итерационный метод называется двухслойным, если для вычисления текущей итерации используются только элементы текущей и предыдущей итераций.Замечание. Определенный выше итерационный метод также можно называть одношаговым.В этом случае для того, чтобы начать процесс построения последовательности , необходимо задать начальное приближение 0 . Далее будем предполагать, что начальное приближение уже задано.Рассмотрим в качестве примера два простейших из двухслойных итерационных методов: метод Якоби и метод Зейделя.Метод ЯкобиМетод Якоби является явным итерационным методом и задается уравнением −+1=−1∑︀=1 −∑︀=+1 , = 1, , ∈ Z+ .Забегая вперед, заметим, что метод Якоби является легко реализуемым, но при этом медленно сходящимся.§5.

Примеры и канонический вид итерационных методов решения СЛАУ19Метод ЗейделяМетод Зейделя, в отличие от метода Якоби, является неявным итерационным методом изадается уравнением −+1=−1∑︀=1 +1 −∑︀=+1 = 1, , ∈ Z+ .,В правой части уравнения используются координаты ( + 1)-ой итерации, поэтому методЗейделя является неявным. Но если разумно организовать вычисления, то можно найтикоординаты ( + 1)-ой итерации по явным формулам.Рассмотрим метод Зейделя при = 1:1 −∑︀=2+1=11 ,11 ∈ Z+ .Видно, что +1находится по явной формуле.

Рассмотрим вторую координату ( + 1)-ой1итерации:∑︀−2 2 − 21 +11=3+1=222, ∈ Z+ .можно найти по явной формуле.известна, то координату +1Так как координата +121Продолжая вычисления, получим, что каждый элемент ( + 1)-ой итерации можно найти по явным формулам от уже известных элементов. Заметим, что метод Зейделя проств реализации, но медленно сходится.Каноническая запись итерационных методовДля исследования сходимости итерационных методов удобно записывать их в матричномвиде. Представим матрицу в виде = 1 + + 2 ,где 1 — нижнетреугольная матрица с нулевой главной диагональю, — диагональнаяматрица, 2 — верхнетреугольная матрица с нулевой главной диагональю:⎛⎞⎛⎞⎛⎞0 12 · · · 100 ··· 011 0 · · ·0⎜ 21⎜ 0 22 · · ·⎜0 0 · · · 2 ⎟0 · · · 0⎟0 ⎟⎜⎟⎜⎟⎜⎟1 = ⎜ .,=,=⎟⎜⎟⎜ ...........

⎟ .2.. .⎠.......... ⎠⎝ ..⎝ ..⎝.. ..... ⎠1 2 · · · 000· · · 00···0Перепишем матричное уравнение (1) в виде(1 + + 2 ) = .Оставим в левой части слагаемое с матрицей , остальные слагаемые перенесем в правуючасть уравнения: = − 1 − 2 .Предположим, что матрица обратима ( ̸= 0, = 1, ). Тогда получим: = −1 − −1 1 − −1 2 .(3)20Глава 1. Численные методы линейной алгебрыЗапишем итерационные методы Якоби (МЯ) и Зейделя (МЗ) исходя из уравнения (3):МЯ : +1 = −1 − −1 1 − −1 2 , ∈ Z+ ,МЗ : +1 = −1 − −1 1 +1 − −1 2 , ∈ Z+ .Рассмотрим эти два метода без обращения матрицы :МЯ : +1 + (1 + 2 ) = , ∈ Z+ ,МЗ : ( + 1 )+1 + 2 = , ∈ Z+ .Перепишем эти соотношения в видеМЯ : (+1 − ) + = ,МЗ : ( + 1 )(+1 ∈ Z+ ,(4)− ) + = , ∈ Z+ .(5)Из формул (4) и (5) видно, что если в каждом из методов последовательность итерацийсходится, то она сходится к решению системы (1).Мы видим, что один и тот же итерационный метод можно записать различными способами.

Поэтому целесообразно ввести какую-то стандартную (каноническую) форму записиитерационных методов.Определение. Канонической формой записи двухслойного итерационного метода решения системы (1) называется его запись в виде+1+1 − + = ,+1(6)где ∈ Z+ , начальное приближение 0 задано, +1 — положительное вещественное число, называемое итерационным параметром, +1 — некоторая обратимая матрица.Определение. Если в методе (6) параметр +1 и матрица +1 не зависят от номераитерации (+1 = , +1 = ), то такой метод называется стационарным, в противном случае — нестационарным.Определение. Если +1 = , то метод (6) называется явным, в противном случае —неявным.При рассмотрении итерационных методов обычно исследуют достаточные условия, прикоторых данный метод сходится, и оценивают скорость сходимости метода.Рассмотрим далее еще несколько примеров итерационных методов: метод простой итерации, метод Ричардсона и попеременно-треугольный итерационный метод. В этих методахвведение параметров и позволяет увеличить скорость сходимости по сравнению с методами Якоби и Зейделя.Метод простой итерацииМетод простой итерации (метод релаксации) определяется итерационной схемой вида+1 − + = , > 0, ∈ Z+ , 0 — задано.(7)§5.

Характеристики

Список файлов лекций