Численные методы. Ионкин (методичка) (2015) (1160451), страница 2
Текст из файла (страница 2)
Итерационные методы (методы Якоби, Зейделя, попеременно-треугольный итерационный метод и другие), в которых задается начальное приближение 0 и итерационный процесс, по которому строится — последовательность приближений, такая,что ‖ − ‖ < ( > 0 — точность приближения).Эффективность итерационного метода определяется числом итераций 0 = 0 (),необходимых для получения решения с заданной точностью .Поиск собственных значений матрицыЗадача нахождения собственных значений матрицы (×) состоит в решении уравнения = , ̸= .(2)Здесь — собственное значение, — собственный вектор. Собственные значения находятсяиз уравнения | − | = 0, которое в общем случае представляет из себя многочлен степени .
Однако, как было доказано Абелем и Галуа, при > 5 данное уравнение не имеетобщего решения в радикалах. Таким образом, в общем виде задачу можно решить тольковычислительными методами.§2. Связь метода Гаусса с факторизацией матрицы9Рассматривают две проблемы поиска собственных значений:1. Частичная проблема собственных значений — нахождение отдельных собственных значений (например, максимального и минимального по модулю).2. Полная проблема собственных значений (для решения часто используется метод –разложения матрицы ) — нахождение всех собственных значений матрицы.Нахождение обратной матрицыОпределение.ет равенствамМатрица −1 называется обратной к матрице , если она удовлетворя−1 = −1 = .Из курса линейной алгебры известно, что если найдена матрица, обратная к матрице , например, в задаче поиска решения системы линейных уравнений (1), то решениенаходится очень просто: = −1 .
В дальнейшем будем активно использовать понятиеобратной матрицы не только в контексте прямого поиска решения, но и при исследованиина сходимость численных методов нахождения решений различных задач и оценке скоростиих сходимости.§2Связь метода Гаусса с факторизацией матрицыРассмотрим матричное уравнение вида(1) = ,где || ̸= 0, ( × ), = (1 , 2 , . . . , ) , = (1 , 2 , . . . , ) . Матрица , вообщеговоря, может быть матрицей с комплексными элементами.Рассмотрим факторизацию (разложение в произведение) матрицы ( × )(2) = · ,где — нижняя треугольная матрица,на главной диагонали:⎛110 ···⎜ 21 22 · · ·⎜=⎜ .....⎝ ....а — верхняя треугольная матрица с единицами00...⎞⎟⎟⎟,⎠1 2 · · · ⎛⎞1 12 · · · 1⎜0 1 · · · 2 ⎟⎜⎟ = ⎜... . ...
⎟ .⎝ ..... ⎠0 0 ··· 1Ясно, что не любую матрицу можно представить в виде (2). В дальнейшем покажем,что нахождение элементов матриц и возможно при определенном ограничении наматрицу . Запишем выражение элемента матрицы = как произведение -йстроки матрицы и -ого столбца матрицы : =∑︁ .=1Выделим -ое слагаемое: =−1∑︁=1 + +∑︁=+1 .10Учитывая структуру матрицы ( = 0, > , = 1), получим = −−1∑︁ , > .(3)=1Аналогично, в определении элемента матрицы выделим -ое слагаемое: =−1∑︁ + +=1∑︁ .=+1Исходя из вида матрицы ( = 0, > ), получим = −−1∑︁ .=1Предполагая, что ̸= 0, поделим левую и правую части уравнения на : −−1∑︀ =1 =, < .(4)Уравнения (3) и (4) позволяют сформулировать следующий алгоритм нахождения элементов матриц и .1.
Положим 11 = 11 . Найдем элементы 1-й строки матрицы :1 =1,11 = 2, .2. Рассмотрим элементы 1-ого столбца матрицы :1 = 1 , = 2, .3. Положим 22 = 22 − 21 12 . Далее, аналогично первому шагу, найдем элементы 2-йстроки матрицы по формулам:2 =2 − 21 1,22 = 3, .4. Вычислим элементы 2-ого столбца матрицы аналогично второму шагу:2 = 2 − 1 12 , = 3, .5.
Повторяя последовательно шаги алгоритма для столбцов матрицы и строк матрицы , найдем все элементы матриц и .Пусть все угловые миноры матрицы отличны от нуля. Тогда представление матрицы в виде (2) существует и единственно.Утверждение.§2. Связь метода Гаусса с факторизацией матрицы11⎞⎛11 . . . 1(︂)︂11 12⎜..
⎟ , = 1, ...Доказательство. Обозначим |1 | = 11 ≠ 0, 2 =, . . . , = ⎝ ..... ⎠21 221 . . . Поскольку | | ≠ 0, = 1, , введем для определенности |0 | = 1. Ясно, что = · , = 1, ,где и матрицы угловых миноров -го порядка для матриц и соответственно.Вычислим значение определителя матрицы , приняв во внимание вид матриц и и равенство | | = 1:| | = | || | = 11 22 · . . . · −1,−1 ,⏟⏞|−1 |Следовательно, =| |̸= 0,|−1 | = 1, .Таким образом, факторизация матрицы в виде (2) существует и определяется единственным образом.Показать, что для вычисления элементов матриц и по формулам (3)3и (4) требуется 3− умножений и делений.
(Число умножений и делений далее будемназывать числом операций.)Задача.Оценим необходимое число операций для вычисления элементов по формуле (3). Для вычисления фиксированного потребуется ( − 1) умножение. Зафиксировав и учитывая, что > , получимРешение.∑︁( − 1) ==1( − 1).2Далее, варьируя от 1 до , получим(︃ )︃(︂)︂∑︁( − 1)1 ∑︁ 2 ∑︁( − 1)( + 1)1 ( + 1)(2 + 1) ( + 1)= −−=. =222626=1=1=1Оценим необходимое число операций для вычисления элементов по формуле (4).Для вычисления фиксированного потребуется ( − 1) умножение и одно деление.
Прификсированном получим−1∑︁( − 1)=.2=1Далее, варьируя от 1 до , получим аналогичную формулу:∑︁( − 1)=12=( − 1)( + 1).6Сложив необходимое число операций для вычисления и , получим искомый результат:( − 1)( + 1) ( − 1)( + 1)3 − +=.66312Классическим методом решения СЛАУ вида (1) является метод Гаусса.Кратко напомним, в чем он заключается:Замечание.1.
Прямой ход. С помощью элементарных преобразований матрица [| ], получаемаяприписыванием к матрице вектор-столбца правых частей системы уравнений (1), приводится к матрице [′ | ′ ], где ′ — верхняя треугольная матрица с единицами на главной диагонали:[| ] → . . . → [′ | ′ ].На этом этапе мы получили новую СЛАУ′ = ′ ,(5)эквивалентную данной: ее решение совпадает с решением исходной задачи.2. Обратный ход метода Гаусса. Последовательно, начиная с последнего уравненияСЛАУ (5) и поднимаясь к первому, по явным формулам вычисляются все компоненты решения системы.Число действий, необходимое для преобразований матрицы в прямом ходе метода Гаусса3равно 3− .
Подробный подсчет числа действий можно найти, например, в [8] c. 13.Заметим, что матрица ′ , к которой приводится матрица в прямом ходе методаГаусса, в точности совпадает с матрицей , полученной в результате факторизацииматрицы в виде (2). Таким образом факторизация матрицы в виде (2) требуеттакое же число действий, что и сведение матрицы к ′ в прямом ходе метода Гаусса.В матричном уравнении (1) подставим = : = , обозначим = и получимдве системы уравнений с треугольными матрицами:{︂ = (6) = (1 , . . . , ) .
= ,(7)Запишем -ое уравнение системы (6):1 1 + 2 2 + . . . + = , = 1, .Предполагая, что ̸= 0, получим − =−1∑︀ =1.Для вычисления требуется ( − 1) умножение и 1 деление — всего операций. Учитывая,что изменяется от 1 до , получим, что для решения системы (6) требуется 1+2+. .
.+ =(+1)операций.2На вычисление новых правых частей, т.е. вектора ′ , в методе Гауссауходитдействий. Как мы можем видеть, это число совпадает с числом операций,необходимых для вычисления вектора y при решении системы (6).Замечание 1.(+1)2Аналогично, запишем -ое уравнение системы (7): + ,+1 +1 + . . . + = , = −∑︁ , = 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) к решению систем линейных уравнений с матрицей .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
