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