Lections-mini (1160453), страница 2
Текст из файла (страница 2)
− ‖ − ‖ = ⎷Теорема 2→∞=1Пусть = * > 0. Тогда метод Якоби сходится в среднеквадратичнойнорме при любом начальном приближении, если выполнено неравенство:Следствие 1.2 > ,где = 1 + + 2 , = diag(11 , 22 , . . . , ).Пусть положительная симметричная матрица ( = * > 0) являетсяматрицей со строгим диагональным преобладанием:Следствие 2. >∑︁| |, = 1, .=1,̸=Тогда метод Якоби сходится в среднеквадратичной норме при любом начальном приближении 0 .Задача.Пусть матрица = * > 0. Доказать, что > 0, = 1, .Пусть = * > 0. Тогда метод Зейделя сходится в среднеквадратичнойнорме при любом начальном приближении 0 .Следствие 3.Следствие 4.Пусть = * > 0, 2 = max > 0.
Если 0 < <16622 ,то метод простойитерации сходится в среднеквадратичной норме при любом начальном приближении 0 .§7Оценка скорости сходимости итерационных методовДля[︂]︂достижения заданной точности достаточно провести число итераций, равное 0 () =1ln , где [] — целая часть числа .ln 1Определение.Величина ln1называется скоростью сходимости итерационного метода.*√︀ Пусть = > 0. Введем энергетическую норму, порождаемую оператором : ‖‖ =(, ).В пространстве существует ортонормированный базис { } из собственных векторовоператора .(об оценке скорости сходимости). Пусть = * > 0, = * > 0.
Пустьтакже существует число , 0 < < 1, такое, что выполнено операторное неравенство:Теорема 11−1+66.(1)8Тогда для погрешности итерационного метода = справедлива оценка:‖ +1 ‖ 6 ‖ ‖ ,Замечание.+1 −+ = решения системы(2) ∈ Z+ .Оценка (2) справедлива и в энергетической норме ‖·‖ .Пусть , — самосопряженные положительно определенные операторы,и пусть существуют 2 > 1 > 0, для которых выполняется условие 1 6 6 2 .2Тогда, если = 0 = 1 +, то двухслойный итерационный метод решения системы урав2нений сходится, и верна оценкаСледствие 1.(3)‖+1 − ‖ 6 ‖ − ‖ ,где =1−1+ ,=12 .Для мутода простой итерации, пусть — самосопряженный положительно определенный оператор, а 1 и 2 — его минимальное и максимальное собственные2значения: 1 = min166 , 2 = max166 .
Кроме того, пусть = 1 +2 . Тогда вернаСледствие 2.оценка ‖+1 − ‖ 6 ‖ − ‖, где =§81−1+ ,=12 .ПТИМИсследование скорости сходимостиЗапишем каноническую форму попеременно-треугольного итерационного метода (ПТИМ):( + 1 )( + 2 )+1 − + = , > 0, > 0, ∈ Z+ .Обозначим = ( + 1 )( + 2 ).(о сходимости ПТИМ). Пусть — самосопряженный положительно определенный оператор и > 4 . Тогда ПТИМ сходится в среднеквадратичной норме при любомначальном приближении 0 .Теорема 1(о скорости сходимости ПТИМ). Пусть — самосопряженный положительноопределенный оператор и числа > 0, ∆ > 0 таковы, что выполняются неравенстваТеорема 2 > , 2* 2 6Положим =√2 ,Δ =21 +2 ,√1 =2(︁∆.4)︁√√ Δ√,+ Δ(1)√Δ4 .√1− √1+3 ,2 =имеет место оценка ‖+1 − ‖ 6 ‖ − ‖ , где =Тогда ПТИМ сходится и=Δ.ПТИМ сходится на порядок быстрее метода простой итерации, метода Зейделя и ме-тода Якоби.
В практических(︀ −2 )︀ задачах, когда велико, отношение = Δ часто(︀ )︀ являетсявеличиной порядка O . Оценим скорость сходимости(︀ ПТИМ:()=O . Оценим0)︀2скорость сходимости метода простой итерации: 0 () = O .§9. Методы решения задач на собственные значения§99Методы решения задач на собственные значенияСтепенной методРассмотрим частичную проблему собственных значений.
Будем искать собственный векторпо формуле+1 = , ∈ Z+ , 0 задано.(1)Пусть { }=1 — собственные значения матрицы , среди которых могут быть повторяющиеся. Упорядочим их по неубыванию модулей: |1 | 6 |2 | 6 . . . 6 | |.Будем доказывать сходимость степенного метода при выполнении трех условий:A) В вещественном пространстве R существует базис { }, = 1, из собственныхвекторов матрицы .⃒⃒⃒⃒B) ⃒ −1⃒ < 1.C) 0 = 1 1 + 2 2 + . . . + , где ̸= 0.Пусть вещественная матрица (×) такова, что выполнены условияA) – C). Тогда степенной метод для матрицы сходится по направлению к собственномувектору, отвечающему максимальному по модулю собственному значению: −→ .→∞}︁{︁+1()()Кроме того, для последовательности , заданной одной из формул = , =Утверждение. , )()1, , либо = ( , )((︃(︂)︂ )︃−1.справедлива следующая оценка сходимости к :()− =OЗамечание.
Пусть у вещественной матрицы ( × ) существует комплексное собственное значение: = 0 + 1 , 1 ̸= 0. Тогда соответствующий собственный вектор —комплексный: = 0 +1 , 1 ̸= , и начальное приближение 0 вектора в итерационномметоде также должно быть комплексным.Метод обратных итерацийПусть матрица — невырожденная. Рассмотрим следующую форму записи неявного итерационного метода: +1 = , ∈ Z+ , 0 задано.Сформулируем три условия:A) В пространстве R существует базис { } из собственных векторов матрицы .⃒ ⃒⃒ ⃒B) ⃒ 21 ⃒ < 1.C) 0 = 1 1 + 2 2 + .
. . + , 1 ̸= 0.Пусть невырожденная вещественная матрица ( × ) такова, чтовыполнены условия A) – C). Тогда метод обратных итераций сходится по направлению ксобственному вектору, отвечающему минимальному по модулю собственному значению: −→ 1 .Утверждение.→∞Задача.Пусть выполнены условия A) – C) сходимости метода обратных итераций.10Показать, что(︃в случаепроизвольной матрицыследующие оценки:)︃(︃(︂ )︂ справедливы(︂ )︂ )︃ 11=O1 − +1, 1 − ((+1,,) ) = O. Показать, что если матрица —22(︃(︂ )︂ )︃2самосопряженная, то последнюю оценку можно улучшить: 1 − ((+1,,) ) = O12.Метод обратных итераций со сдвигомРассмотрим итерационный метод, задаваемый формулой (−)+1 = , ∈ Z+ , 0 задано,где — такое вещественное число, что матрица ( − ) невырождена.(︃)︃()Само собственное значение находится из выражения: = lim→∞+(),=+11, .§10Приведение матрицы к верхней почти треугольной формеМатрица имеет⎛ верхнюю× × ×⎜× × ×⎜⎜0 × ×⎜ее можно записать в виде = ⎜ 0 0 ×⎜⎜.
. .⎝ .. .. ..Определение.почти... ×... ×... ×... ×.... ..треугольнуюформу (ВПТФ), если⎞××⎟⎟×⎟⎟, где символами × обозначены,×⎟⎟⎟.. ⎠.0 0 0 ... × ×вообще говоря, ненулевые элементы матрицы.Элементарным отражением, соответствующим вещественному векторстолбцу = (1 , 2 , . . . , ) , называется преобразование, задаваемое матрицейОпределение. =−212⎜ 2 1⎜ = ⎜ .⎝ ..⎛ .‖‖2(1)⎞· · · 1 · · · 2 ⎟⎟.. ⎟ — симметричная (эрмитова) матрица..... ⎠2 1 2 · · · Сформулируем свойства матрицы элементарного отражения:1 222...1. H — симметрическая матрица, = .2. H — ортогональная матрица, −1 = .Пусть задан вещественный вектор-столбец = (1 , 2 , .., ) .
Тогдаможновыбрать вектор так, чтобы было выполнено равенство = (−‖‖, 0, 0, .., 0) , ‖‖ =√︀(, ), где H — элементарное отражение, соответствующее вектор-столбцу .Утверждение.Любую вещественную матрицу ( × ) можно привести к верхнейпочти треугольной форме с помощью преобразования подобия с ортогональной матрицейУтверждение.§11. Понятие о QR-алгоритме решения полной проблемы собственных значений⎛× × × ...⎜× × × . . .⎜⎜0 × × ...⎜: = −1 = ⎜ 0 0 × . . .⎜⎜. .
. ...⎝ .. .. ..0 0 0 ...Замечание 1.××××...11⎞××⎟⎟×⎟⎟, где = −1 .×⎟⎟.. ⎟.⎠× ×Преобразование подобия сохраняет спектр матрицы: = , = 1, .Если — симметрическая матрица, то также является симметрической матрицей: = ⇒ = .Замечание 2.Замечание 3. Симметричная матрица, имеющая верхнюю почти треугольную форму,является симметричной трехдиагональной матрицей.§11Понятие о QR-алгоритме решения полной проблемы собственных значенийПроизвольная матрица (×) может быть представлена в виде: =, где — ортогональная матрица, а — матрица, имеющая верхнюю треугольнуюформу (ВТФ).Утверждение.Число операций, необходимых для вычисления QR-разложения матрицы ,зависит от вида матрицы .
Для произвольной матрицы число операций можно оценить величиной порядка 3 , для матрицы с ВПТФ, — порядка 2 , для трехдиагональнойматрицы — порядка .Замечание.Рассмотрим оптимальную версию QR-алгоритма. Приведем матрицу к матрице 0 ,имеющей ВПТФ, и осуществим QR-разложение матрицы 0 : 0 = 0 0 , где 0 — ортогональная, а 0 — верхнетреугольная матрица. Построим матрицу 1 = 0 0 .На следующем шаге осуществим QR-разложение матрицы 1 = 1 1 и построим матрицу 2 = 1 1 . Аналогичным образом продолжая вычисления, на -м шаге осуществимQR-разложение матрицы = и построим +1 = .Если все собственные значения матрицы вещественны,⎛ то последова-⎞1 × . .
. ×⎜ 0 2 . . . × ⎟⎜⎟тельность матриц { } сходится к матрице, имеющей ВТФ: −→ ⎜ ... . ... ⎟ ..→∞ ⎝ .. . ⎠.0 0 . . . Если же матрица имеет комплексную пару собственных значений 0 ± 1 , то ей наглавной ⎛диагонали предельной матрицыбудет соответствовать клетка размера 2 × 2:⎞×⎜⎟×⎟⎜⎟⎜0 1⎜⎟ −→ ⎜⎟ . (без доказательства)−1 0⎟→∞ ⎜⎜⎟..⎝⎠.0×Утверждение.Итерационный процесс останавливается, когда все элементы ниже главной диагонали, либо ниже побочной (в случае комплексно-сопряженных собственных значений) матрицы при некотором становятся равными нулю. Однако следует заметить, что в данном случае под нулем мы понимаем либо машинный ноль, либо число,меньшее некоторой заданной величины — необходимой точности вычисления.Замечание 1.12Замечание 2.QR-алгоритм применим к произвольной матрице .QR-алгоритм является очень затратным по необходимому числу операций и объему памяти, используемому для хранения промежуточных матриц.Замечание 3.§12Предварительное преобразование матрицы к ВПТФ.
Неухудшение ВПТФ при QR-алгоритмеЛемма 1.Пусть = , где имеет ВТФ, а имеет ВПТФ. Тогда имеет ВПТФ.Лемма 2. Пусть = , где — матрица с ВПТФ, а — матрица с ВТФ. Тогда —матрица с ВПТФ.Глава IIИнтерполирование и приближениефункцийГлава вырезана по причине отсутствия её на лекциях :)§13Постановка задачи интерполирования§14Интерполяционная формула Лагранжа§15Разделенные разности§16Интерполяционная формула Ньютона§17Интерполирование с кратными узлами.
Полином Эрмита§18Использование интерполяционного полинома Эрмита 3 ()для оценки погрешности квадратурной формулы Симпсона§19Наилучшее среднеквадратичное приближение функции§20Наилучшее среднеквадратичное приближение функций,заданных табличноГлава IIIЧисленное решение нелинейныхуравнений и систем нелинейныхуравнений§21Способы локализации корней нелинейного уравненияПостановка задачи. () = 0.(1)Рассмотрим функцию (), ∈ R, и уравнение () = 0 Пусть * — вещественный корень уравнения, и определена его окрестность радиуса , не содержащая других корнейуравнения: (* ) = { : | − * | < }, причем заданная функция () определена наэтой окрестности. Будем считать, что начальное приближение 0 ∈ (* ) задано.Тогда для нахождения численного решения уравнения в рассматриваемой окрестностинеобходимо построить последовательность { }, сходящуюся к корню * уравнения (1):lim→∞ ( ) = (* ) = 0.Первый прием локализации корняПусть задано разбиение сегмента [, ]: 6 0 < 1 < 2 < .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
