main (1160446), страница 3
Текст из файла (страница 3)
. + = , = −∑︁ , = 1, .=+1Для вычисления требуется ( − ) умножений. Изменяя от 1 до , получим, что длярешения системы (7) требуется ( − 1) + ( − 2) + . . . + 2 + 1 = (−1)умножений.2§3. Обращение матрицы методом Гаусса-ЖорданаЗамечание 2.Гаусса, равномы (7).13Число операций, затрачиваемых на выполнение обратного хода методачто совпадает с числом действий, требуемых для решения систе-(−1),2В итоге получим, что для решения систем (6) и (7) требуется (−1)+ (+1)= 222операций. Тогда все решение системы (1) с использованием факторизации матриц требует32 −3 −+ 2 = +3операций, что равно общему числу операций, необходимых для33решения этой же системы методом Гаусса.
Таким образом, решение системы (1) методомГаусса эквивалентно по числу операций факторизации матрицы и решению двух системуравнений.Поясним, в каких случаях выгодно решать СЛАУ (1) именно с использованием факторизации вместо классического метода Гаусса. На практике: как правило,решаются целые серии задач с одной и той же матрицей , которая описывает математическую модель изучаемого объекта или процесса, и с различными правыми частями ,которые соответствуют изменяющимся входным условиям. Таким образом, можно одинраз факторизовать матрицу , а затем для нахождения решения каждой задачи решатьлишь СЛАУ вида (6) и (7) для каждого наблюдения.
Так как в методе Гаусса наибольшеечисло действий требуется на преобразование матрицы к верхнему треугольному виду3( 3− ), то решая серию СЛАУ с фиксированной матрицей с использованием факто3ризации, разложение = осуществляется лишь один раз, затрачивая на это 3−действий, а затем решается серия СЛАУ с меняющимися правыми частями. В итоге,общее число операций на решение серии СЛАУ будет меньше, чем при решении той жесерии классическим методом Гаусса. Этот выигрыш будет виден при решении задачиобращения невырожденной матрицы.Замечание 3.§3Обращение матрицы методом Гаусса-ЖорданаРассмотрим задачу обращения (поиска обратной матрицы) невырожденной матрицы (×).
Согласно критерию обратимости матрицы, для невырожденной матрицы всегда существует обратная. Введем обозначение: −1 = = ( ), , = 1, . С учетом этого задачаобращения матрицы состоит в решении системы = ,(1)где ( × ), || ≠ 0, или, если записать поэлементно:∑︁ = , = 1, , = 1, .(2)=1Можно приступить к решению последней системы методом Гаусса без учета структурыматрицы коэффициентов. Эта система имеет 2 неизвестных переменных, число требуемых для решения операций будет пропорционально 6 .
Покажем, что существует способобращения матрицы, требующий ровно 3 операций. Более того, в случае, если матрица имеет специальную структуру (например, если матрица — блочная или трехдиагональная), число операций уменьшится.Сведем уравнение (2) к решению систем линейных уравнений с матрицей . Для этоговведем вектор-столбец матрицы : () = (1 , 2 , .
. . , ) и вектор-столбец правойчасти () = (0, 0, . . . , 0, 1, 0, . . . , 0) с единицей на -й позиции. Теперь можем записатьматричное уравнение (1) в виде систем: () = () , = 1, .(3)14Факторизуем матрицу в виде(4) = · .Для этого требуетсянений:3 −3умножений и делений. Получаем две системы линейных урав-{︃ () = () ,()=()(5) = 1, ,(6).При фиксированном решение систем (5) и (6) потребует 2 действий.
Для решения таких систем при = 1, потребуется 3 действий. Значит, в целом для обращения3матрицы необходимо 3 + 3− ∼ 43 3 операций. Покажем теперь, что это числоопераций можно уменьшить. Рассмотрим систему уравнений (5):11 1 = 0()⇒1 = 0,()()⇒2 = 0,()()⇒3 = 0,21 1 + 22 2 = 0()31 1 + 32 2 + 33 3 = 0()()()...()()−1,1 1 + . . . + −1,−1 −1 = 0()Рассмотрим -ое уравнение: ()⇒ −1 = 0.= 1. Предполагая, что ̸= 0, получим:()=1.(7)Запишем уравнения системы при > ()()() + ,+1 +1 + . . . + = 0, = ( + 1), ,(8)()и выразим из них :−()=−1∑︀=() = ( + 1), .,(9)Перейдем к подсчету числа операций, необходимых для решения систем уравнений (5) и (6).При фиксированных и в формуле (9) получаем ( − ) умножений и одно деление в уравнении (7). Варьируя индекс от 1 до , при фиксированном получаем( − ) + ( − − 1) + .
. . + 1 =( − )( − + 1)2умножений и (− +1) делений. Таким образом, число действий, необходимое для решенияодной системы (5) равно( − + 1)( − + 2)( − )( − + 1) 2( − + 1)+=.222Общее число действий, необходимое для решения всех систем (5) равно∑︁( − + 1)( − + 2)=12.(10)§4. Метод квадратного корняЗадача.15Показать, что сумма (10) равнаРешение.(+1)(+2).6Сделаем замену = − + 1 в формуле (10):∑︁( − + 1)( − + 2)=12=∑︁( + 1)2=1.Преобразовав полученное выражение, получим искомый результат:(︃ )︃(︂)︂( + 1)( + 2)1 ∑︁ 2 ∑︁1 ( + 1)(2 + 1) ( + 1)= ++. =22626=1=1Аналогично получаем, что число операций для решения всех систем вида (6) равно2 (−1).
Просуммируем число операций для факторизации исходной матрицы и для реше2ния систем (5) и (6) при = 1, :3 − ( + 1)( + 2) 2 ( − 1)++= 3 .362Описанный выше метод обращения произвольной невырожденной матрицы называетсяметодом Гаусса-Жордана. Отметим, что он является самым эффективным методом обращения невырожденных матриц произвольного вида.§4Метод квадратного корняОпределение. Квадратная матрица называется эрмитовой (самосопряженной), еслиее элементы связаны соотношением = ). В этом случае будем записывать = * .Рассмотрим задачу(1) = ,где ∈ C× , = * , || ≠ 0, = (1 , 2 , . .
. , ) , = (1 , 2 , . . . , ) , и одиниз прямых методов ее решения — метод квадратного корня (метод Холецкого).Заметим, что хотя класс эрмитовых матриц с точки зрения линейной алгебры достаточно узок, на практике часто возникают модели, описываемые именно этим классом матриц.Поэтому с практической точки зрения такое ограничение на систему (1) вполне допустимо.Факторизуем эрмитову матрицу в виде = * ,(2)где матрица — верхнетреугольная матрица с положительными элементами на главнойдиагонали, а — диагональная матрица со значениями ±1 на главной диагонали:⎛⎞⎛⎞11 0 · · ·011 12 · · · 1⎜ 0 22 · · · 2 ⎟⎜ 0 22 · · ·0 ⎟⎜⎟⎜⎟=⎜ ., > 0,=⎜ .⎟..... ⎟ , = ±1..........⎝ .⎝ ..... ⎠..
⎠00· · · 00· · · Покажем, что факторизация (2) возможна на примере вещественной симметрическойматрицы второго порядка. Не ограничивая общности, будем полагать 11 ̸= 0.(︂)︂11 12== , 12 = 21 .21 2216Матрицы и будем искать в виде(︂)︂11 12=, > 0, = 1, 2,0 22(︂)︂11 0* = =,12 22(︂)︂11 0=, = ±1, = 1, 2.0 22Найдем матрицу :(︂ =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, .§4. Метод квадратного корня17Выделим -ое слагаемое из последней суммы и учтем, что ( * ) = : =−1∑︁ + +=1∑︁ ,, = 1, .=+1Третье слагаемое из равенства равно нулю в силу того, что матрица * является нижнетреугольной: = 0, > . Тогда получим: =−1∑︁ + ,, = 1, .(6)=1Так как матрица эрмитова, достаточно рассматривать это равенство только в случае 6 .
При = получим: =−1∑︁ + , = 1, . | |2 + | |2 , = 1, ,=1Учтем, что = | |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) = ,где || ≠ 0, ( × ), = (1 , 2 , . .
. , ) , = (1 , 2 , . . . , ) .Распишем систему (1) покоординатно:∑︁(2) = 1, . = ,=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)-й итерации, поэтому методЗейделя является неявным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
