Lections-mini (1160453)

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

Текст из файла

БлагодарностиМетодичка прошла долгий путь, её начали пытаться создавать давным давно и все этилюди внесли свой вклад, они заслужили, чтобы их знали.1. Набрали первую версию этой методички, именно эти люди сделали основную работуи именно им принадлежит истинная слава (в 2013 году):— В. С. Алтухов— М. А. Казачук— М. В.

Коростелева— С. В. Селецкий— А. В. Фролова,— В. И. Шахуро2. Эти люди были на 2-м подходе и внесли правки (в 2015 году).— Иванов Д. И.— Кислых Д. М.— Шохин К. О3. Методички были созданы по лекциям и с некоторой помощью преподавателей:— профессор А. В. Гулин— доцент Н. И. Ионкин1. Данный документ – мини-методичка и является грубо урезанной версией методичкисозданной в 2015 году— Василенко А.Э.2. Было бы хорошо, если бы кто-то взялся окончательно облагородить данную миниметодичку.Глава IЧисленные методы линейной алгебрыЗадача нахождения собственных значений матрицы (×) состоит в решении уравнения(1) = , ̸= .Здесь — собственное значение, — собственный вектор.Определение.ет равенствам§1Матрица −1 называется обратной к матрице , если она удовлетворя−1 = −1 = .Основные задачи главы I(skipped)§2Связь метода Гаусса с факторизацией матрицыРассмотрим матричное уравнение вида(1) = ,где || ̸= 0, ( × ), = (1 , 2 , .

. . , ) , = (1 , 2 , . . . , ) . Матрица , вообщеговоря, может быть матрицей с комплексными элементами.Рассмотрим факторизацию (разложение в произведение) матрицы ( × )(2) = · ,где — нижняя треугольная матрица, а — верхняя треугольная матрица с единицами наглавной диагонали:⎛⎛⎞⎞110 ···01 12 · · · 1⎜ 21 22 · · ·⎜0 1 · · · 2 ⎟0 ⎟⎜⎟⎜⎟=⎜ .,=⎜ ...... ⎟..

. ... ⎟ ...⎝ ..⎠⎝....... ⎠1 2 · · · = −−1∑︁=10 − , > . =0−1∑︀=1···1 , < .(3)§3. Обращение матрицы методом Гаусса-Жордана3Пусть все угловые миноры матрицы отличны от нуля. Тогда представление матрицы в виде (2) существует и единственно.Утверждение.Показать, что для вычисления элементов матриц и по формулам (3) тре3буется 3− умножений и делений. (Число умножений и делений далее будем называтьчислом операций.)Задача.Замечание. Число действий, необходимое для преобразований матрицы в прямом ходеметода Таким образом факторизация матрицы в виде (2) требует такое же числодействий, что и сведение матрицы к ′ в прямом ходе метода Гаусса.{︂(4) = = (1 , .

. . , ) . = ,Замечание 1.уходит(+1)2(5)На вычисление новых правых частей, т.е. вектора ′ , в методе Гауссадействий.Замечание 2.Число операций, затрачиваемых на выполнение обратного хода методачто совпадает с числом действий, требуемых для решения второй(−1),2Гаусса, равносистемы из (4).В итоге получим, что для решения систем (4) требуется (−1)+ (+1)= 2 операций.223Тогда все решение системы (1) с использованием факторизации матриц требует 3− +32 −2 = +3операций3§3Обращение матрицы методом Гаусса-ЖорданаРассмотрим задачу обращения (поиска обратной матрицы) невырожденной матрицы (×).∑︁ = , = , = 1, , = 1, .(1)=1где ( × ), || ≠ 0, при этом количество операций равно3 − ( + 1)( + 2) 2 ( − 1)++= 3 .362Отметим, что он является самым эффективным методом обращения невырожденных матриц произвольного вида.§4Метод квадратного корняКвадратная матрица называется эрмитовой (самосопряженной), еслиее элементы связаны соотношением = ).

В этом случае будем записывать = * .Определение.Факторизуем эрмитову матрицу в виде = * ,(1)4где матрица — верхнетреугольная матрица с положительными элементами на главнойдиагонали, а — диагональная матрица со значениями ±1 на главной диагонали:⎛⎞11 12 · · · 1⎜ 0 22 · · · 2 ⎟⎜⎟=⎜ ... . ... ⎟ , > 0,.⎝ ....

⎠00 · · · ⎛⎞11 0 · · ·0⎜ 0 22 · · ·0 ⎟⎜⎟=⎜ .... ⎟ , = ±1.....⎝ .... ⎠00 · · · Выразим и : = sgn( −−1∑︁| |2 ), = 1, ,(2)=1 −−1∑︀ =1 =, , = 1, , < .(3)Метод квадратного корня позволяет примерно вдвое уменьшить число операций, необ3ходимых для решения системы, по сравнению с методом Гаусса — до ∼ 6 умножений иделений. Кроме этого необходимо операций извлечения квадратного корня.

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

Если в методе (3) параметр +1 и матрица +1 не зависят от номераитерации (+1 = , +1 = ), то такой метод называется стационарным, в противном случае — нестационарным.Определение.неявным.Если +1 = , то метод (3) называется явным, в противном случае —При рассмотрении итерационных методов обычно исследуют условия, при которых данный метод сходится, и оценивают скорость сходимости метода.Метод простой итерацииМетод простой итерации (метод релаксации) определяется итерационной схемой вида+1 − + = , > 0, ∈ Z+ , 0 — задано.(4)Метод РичардсонаМетод Ричардсона определяется итерационной схемой вида+1 − + = , +1 > 0, ∈ Z+ , 0 — задано.+1(5)Замечание.

Для итерационных методов (4) и (5) в случае, когда матрица являетсясимметричной и положительно определенной, известен такой набор итерационных параметров (Чебышевский набор), при котором сходимость этих методов будет наиболеебыстрая.Попеременно-треугольный итерационный методПредставим матрицу в виде = 1 + 2 , где 1 — нижнетреугольная матрица, 2 —верхнетреугольная матрица:⎛⎞⎛⎞0.5110···00.51112···1⎜ 21⎜ 00.522 · · ·0 ⎟0.522 · · ·2 ⎟⎜⎟⎜⎟1 = ⎜ .,=⎜ ......

⎟.... ⎟ .2....⎝ ..⎝⎠....... ⎠12 · · · 0.500· · · 0.5Попеременно-треугольный метод имеет вид+1 − + = , ∈ Z+ ,где > 0, > 0 — итерационные параметры( + 1 )( + 2 )(6)6Определение.§6Вектор = − называется невязкой на -й итерации.Теоремы о сходимости итерационных методовРассмотрим матричное уравнение вида = ,(1)где || ≠ 0, ( × ), = (1 , 2 , . . .

, ) , = (1 , 2 , . . . , ) .Рассмотрим также двухслойный стационарный метод решения уравнения (1):+1 − + = ,(2)где ∈ Z+ , начальное приближение 0 задано, — положительное вещественное число, — обратимая матрица порядка ( × ).(︂ )︂ 1√︀∑︀ 2 2Введем евклидову норму: ‖‖ = (, ) =.

Эту норму также часто называютсреднеквадратичной нормой.=1Линейный оператор называется положительным (неотрицательным),если (, ) > 0 ∀ ∈ , ̸= (соответственно (, ) > 0 ∀ ∈ ). Положительностьоператора обозначается как > 0.Определение.Скалярным произведением в смысле оператора называется скалярноепроизведение, определяемое соотношением (, ) = (, ).Определение.Энергетической нормой, порождаемой линейным самосопряженным положительноопределеннымоператором , называется норма, задаваемая соотношением√︀√︀‖‖ = (, ) = (, ).Определение.Задача.Пусть = * > 0.

Доказать, что ∃ > 0 : (, ) > (, ) = ‖‖2 .Рассмотрим свойства положительного самосопряженноголинейного(︁)︁*(︁ 1 )︁* оператора.(︁)︁11 *1*−1−1Если = > 0, то определены = > 0, 2 = 2 > 0, − 2 = − 2 >0.Определение.векторПогрешностью итерационного метода на -й итерации называется = − .(3)Определение.Итерационный метод сходится в норме ‖·‖, если ‖ ‖ → 0 при → ∞.Определение.Матрица = − −1 называется матрицей перехода от -й итера-ции к ( + 1)-й.Итерационный метод (2) решения системы (1) сходится при любом начальном приближении тогда и только тогда, когда все собственные значения матрицыперехода по модулю меньше единицы.

(Без доказательства)Теорема 1.Заметим, что данная теорема практически неприменима, так как задача нахожденияполного спектра матрицы аналитически решается крайне редко.§7. Оценка скорости сходимости итерационных методов7(теорема Самарского). Пусть — самосопряженный положительно определенный оператор, — положительное вещественное число и выполнено операторное неравенство − > 0.(4)2Тогда итерационный метод (2) решения системы (1) сходится в среднеквадратичнойнорме при любом начальном приближении:⎯⎸∑︁)︁2⎸ (︁ −→ 0, ∀0 .

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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