main (1160446), страница 2
Текст из файла (страница 2)
В главе I рассматриваются прямые и итерационныечисленные методы решения систем линейных алгебраических уравнений, а также исследуются итерационные методы решения частичной и полной проблем собственных значений. Вглаве II представлены методы интерполирования и приближения функций. В главе III описаны методы решения нелинейных уравнений и систем нелинейных уравнений. На практикечасто встречается задача численного решения дифференциальных уравнений, которой посвящены главы IV и V. Так, в главе IV приводятся описание и анализ разностных методоврешения задач математической физики.
А в заключительной, пятой, главе рассматриваются методы численного решения задач Коши для обыкновенных дифференциальных уравнений.В приложении А размещена информация об ученых, упомянутых в тексте, которая была взята из интернета. Информация носит ознакомительный характер, не претендует наоригинальность и, надеемся, будет весьма интересна читателю.Список обозначенийN — множество натуральных чисел: {1,2, . . . };Z — множество целых чисел;Z+ — множество целых неотрицательных чисел;R — множество вещественных чисел;R+ — множество вещественных неотрицательных чисел;C — множество(︀)︀ комплексных чисел; () = O () — функция асимптотически ограничена сверху функцией (с точностьюдо постоянного множителя); () — вектор-функция;[] — целая часть числа .В следующих обозначениях и — натуральные числа.
( × ) — вещественная (если не сказано иное) матрица , содержащая строк и столбцов;R× — множество всех матриц размера × над полем вещественных чисел;C× — множество всех матриц размера × над полем комплексных чисел.Размер следующих матриц и вектора определяется по контексту. — нулевой вектор-столбец; — единичная матрица;0 — нулевая матрица; — конец доказательства; — символ Кронекера:{︃1 при = , =0 при ̸= .Глава IЧисленные методы линейной алгебры§1Основные задачи главы IРешение систем линейных уравненийРассмотрим матричное уравнение вида = ,(1)где || ≠ 0, ( × ), = (1 , 2 , . .
. , ) , = (1 , 2 , . . . , ) .Так как матрица невырождена, то решение системы (1) существует иединственно (см. [7], гл.VI, стр.104). Существуют две группы методов решения СЛАУ:1. Прямые методы (методы Гаусса, Крамера, Холецкого и другие (см. [1], [4])), позволяющие за конечное число действий получить решение задачи. Эффективность методовэтой группы оценивается по необходимому числу умножений и делений. Несмотря нато, что эти методы часто называют точными, прямые методы таковыми не являютсяиз-за ошибок округления при вычислении.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 + . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
