Н.И. Ионкин - Электронные лекции (2010), страница 5

Тогда.Доказательство.∑︀()1− − ( , )( , ),=1=== ∑︀(+1 , )−−1 − ( , ),=1(︂2 −21 1 (1 , 1 ) 1 +(︂=2 −2−11 1(1 , 1 ) 1 +2 (1 ,2 )1 (1 ,1 )2 (1 ,2 )1 (1 ,1 )(︁ )︁−21(︁ )︁−21+ ··· +(︁1(︁1+ ··· +(︂(︂ )︂ )︂1= 1 + 2(︂(︂ )︂ )︂1()1 − 1 = 2)︁2)︁2( , )(1 ,1 )(︁1( , )(1 ,1 )(︁1()1)︁−2 )︂)︁−2−1 )︂ == 1 +Приведение матрицы к верхней почти треугольной форме (ВПТФ)33Сформулируем еще одно утверждение:Утверждение.

Если есть хотя бы одно комплексное собственное значение = 0 + 1 ,1 ̸= 0,то и отвечающий ему собственный вектор должен быть комплексным, и начальноеприближение для него должно быть комплексным.Доказательство. Пустьзначению = 0 + 1 . = 0 +1 - собственный вектор матрицы A, отвечающий собственномуТогда: = (0 + 1 ) = (0 + 1 )(0 + 1 ) = 0 0 − 1 1 + (0 1 + 1 0 )В силу линейности:0 = 0 0 − 1 11 = 0 1 + 1 0Предположим, что1 = 0.

Тогда 1 0 = 0, 0 = 0, откуда следует, что = 0, а это противоречиттому, что x - ненулевой вектор.Метод обратных итераций со сдвигомИногда бывает нужно найти собственное значение из внутренней части спектра. Рассмотримметод обратных итераций со сдвигом:( − )+1 = , ∈ R, ∈ N = 0, 1, . . . ,Пусть существует( − )−1 = ,0тогда получим степенной метод для матрицы B:+1 = , = 0, 1, . .

. ,Собственные значения матрицы B: =Тогда → — задан.0— задан.1−(по направлению), где l таково, что: = max=1,..., 11= − − Замечание. Если известно приближенное значение какого-то собственного значения, а мыхотим его уточнить, то можно использовать этот метод. Найти весь спектр этим методомпрактически невозможно.§10Приведение матрицы к верхней почти треугольной форме(ВПТФ)Легче всего найти собственные значения у диагональной или треугольной матрицы.

Нашазадача - привести матрицу A (m x m) к треугольной. Однако, приведение матрицы A к треугольнойформе методом Гаусса не сохраняет спектр матрицы. Спектр матрицы сохраняется при преобразованииподобия: = −1 Если матрица Q - ортогональна (унитарна), то сохраняется симметрия.Приведение матрицы к верхней почти треугольной форме (ВПТФ)34Определение.

Матрица находится в верхней почти треугольной форме (ВПТФ), если онаимеет вид (ненулевые элементы обозначены через x):⎛⎜⎜⎜0⎜ = ⎜ ..⎜.⎜⎝00Рассмотрим вектор-столбец ··· ··· ···.........0 0 ···0 0 ···⎞ ⎟⎟ ⎟⎟...... ⎟...⎟⎟ ⎠0 : = (1 , 2 , . . . , ) = (1 , 2 , . . . , )Определение. Элементарным отражением, соответствующим вектору , называется преобразование,задаваемое матрицей: =−2 ||||2Замечание.2 = 12 + 22 + · · · + = ||||2⎞⎛1 2 · · · 1 12⎜ 2 122 · · · 2 ⎟⎟⎜ = ⎜ ...... ⎟..⎝ .... ⎠2 1 2 · · · Матрица - симметричная.Свойства оператора H:1.

= 2. −1 = Докажем второе свойство, то есть чтоявляется ортогональной матрицей.Доказательство.(︂)︂ (︂)︂ = = −2−2=|| ||2|| ||22−4Используя свойство ( ) +4|| ||2|| ||4 = || ||2 , сократим в последнем соотношении дроби и получим, что = Значит, матрица H является ортогональной.Сформулируем и докажем свойство 3.Приведение матрицы к верхней почти треугольной форме (ВПТФ)Теорема. Для любого вектора :⎛ 1 ⎞=⎝можно выбрать такой вектор23... = ||||,⎠ = (1 , 2 , . .

. , ), что⎛ − ⎞ = ⎝где3500...0⎠то есть преобразование H подавляет все координаты вектора кроме первой.Доказательство. Выберемв виде: = + , ∈ R, = (1, 0, 0, . . . , 0) = − 2( + )( + )=( + ) ( + ) − ( + )2( + ) ( + ) ( + )Для дальнейшего преобразования воспользуемся свойствами 1 и 2 :( + ) = ||||2 + 1( + ) ( + ) = ||||2 + 1 + 1 + 2 =||||2 + 21 + 2Положим = ||||.Тогда получим:2( + ) = − ( + )( + ) ( + )2 − ( + )222⎛ − ⎞(|||| + 21 + ) + |||| − = − − = ⎝||||2 + 21 + 200...0⎠Полученные 3 свойства мы будем применять при приведении матрицы к верхней почтитреугольной форме.

порядка × :⎛⎞11 12 . . . 1⎜ 21 22 . . . 2 ⎟⎟=⎜⎝. . . . . . . . . . . . . . . . . . .⎠1 2 . . . Пусть дана произвольная матрицаПриведение матрицы к верхней почти треугольной форме (ВПТФ)36Представим ее в виде блочной матрицы следующего вида:(︂=11 −1−1 −1)︂где−1 = (12 , 13 , . . . , 1 )−1 = (21 , 31 , . .

. , 1 )а матрица−1получается из матрицыудалением первого столбца и первой строки.Воспользуемся свойством 3:⎛−1 −1Рассмотрим матрицу1порядка×вида:(︂1 =Очевидно,1 = 1 ,12⎞−||−1 ||⎜⎟0⎜⎟=⎜⎟..⎝⎠.01012021 −1значит:(︂=1012021 −1)︂ (︂1012021 −1Последнее равенство верно в силу того, чтоматрица)︂)︂(︂=10122021 −12−1= - ортогональная.−1Обозначим 1 = 1 111⎜⎜−1 −1⎜01 = ⎜⎜.⎜..⎝0⎞(1)12 . . .⎟(2)22 . . .

⎟(1)(1) ⎟32 ⎟⎟.⎟... . .⎠(1)2 . . .Таким образом, структуру матрицы можно представить так:⎛×⎜×⎜⎜0⎜⎜0⎜⎜ ..⎝.0⎛Возьмем вектор(1)32⎞. ⎟. ⎠.(1)2⎜−2 = ⎝⎞××⎟⎟×⎟⎟×⎟⎟..⎟.......⎠× ... ×××××............=Таким образом, мы получили что1⎛)︂Приведение матрицы к верхней почти треугольной форме (ВПТФ)По свойству 3, можно построить такой оператор−2 ,37что:⎛−2 −2Рассмотрим матрицу2 ,построенную аналогично матрице(︂2 =где2 =⎞−||−2 ||⎜⎟0⎜⎟⎜⎟0=⎜⎟⎜⎟..⎝⎠.02012021 −21)︂(︀ 1 0 )︀0 1Свойства матрицы1.2 = 22.2 = 2−12 :- ортогональная матрицаАналогично, обозначим2 :2 = 2−1 1 2 = 2−1 1−1 1 2Посмотрим на структуру матрицы2 :⎛⎞××⎟⎟×⎟⎟×⎟⎟...⎟.........⎠0 × ...

××⎜×⎜⎜0⎜2 = ⎜ 0⎜⎜ ..⎝.0×××0××××............Очевидно, что сделав таким образом m-2 шага, мы придем к верхней почти треугольнойформе. В итоге мы получим:−1−1 = −2−3. . . 2−1 1−1 1 2 . . . −3 −2 =⎛×⎜×⎜⎜0⎜= ⎜0⎜⎜ ..⎝.0Обозначим×××0××××....................00×.⎞××⎟⎟×⎟⎟×⎟⎟.⎟.⎠.×-ВПТФ = 1 2 . . . −2−1−1 = −2−3. . . 2 1 = −2−3. . . 2−1 1−1 = −1Понятие о QR-алгоритме. Решение полной проблемы собственных значений.38Следовательно, матрица U - ортогональна. = −1 ⇒ ∼ Причем подобие выполняется с помощью ортогональной матрицыЭлементы матрицы C имеют вид: = 0, ≥ + 2, = 1, 2, .

. . , − 2Замечание. Собственные значения матрицы A совпадают с собственными значениями матрицыC, т.е.: = , = 1, Доказательство. = , ̸= 0 −1 = −1 , обозначим −1 = ̸= 0 ⇒ = −1 = , ̸= 0 = Замечание. Если = , то = Доказательство. = ( −1 ) = ( −1 ) = −1 = §11Понятие о QR-алгоритме. Решение полной проблемысобственных значений.Изученные в предыдущем параграфе свойства позволят нам представить матрицу = где−1 = - ортогональная матрица, а в виде:(1)имеет верхнетреугольную форму.Возьмем вектор = (11 , 21 , . .

. , 1 ). Для него существует такая ортогональная матрица1 = − 2 ||, которая “подавляет” все координаты вектора , кроме первой.||2Матрица 1 имеет вид:⎛⎞×⎜0⎜⎜1 = ⎜ 0⎜ ..⎝.0Построим матрицу2 =(︀ 100 )︀порядка× ... ×× . . . ×⎟⎟× . . . ×⎟⎟..⎟.......⎠× ... × × ,такую,чтоПонятие о QR-алгоритме. Решение полной проблемы собственных значений.⎛39⎞× × ... ×× × . . . ×⎟⎟0 × . . . ×⎟⎟⎟....... ×⎠..0 × ... ××⎜0⎜⎜2 1 = ⎜ 0⎜ ..⎝.0Очевидно, что за (m-1) шаг мы обнулим все элементы под главной диагональю:(︃ × ×−1 −2 . . .

2 1 = =0...0×...0............× )︃×××−ВТФПостроим матрицу Q следующим образом: = 1 2 . . . −1Найдем :−1−1 = −1−2. . . 2 1 = −1−2. . . 1−1 = −1Следовательно, матрица Q ортогональна.Таким образом, мы получили разложение матрицы A.Замечание. При факторизации в виде QR:1. Для произвольной матрицы2. Для матрицытребуетсявида ВПТФ требуется3. Для трехдиагональной матрицы(3 )(2 )требуетсядействий.действий.()действий.QR-алгоритмВозьмем матрицу0 .Представим ее в виде0 = 0 0 ,где0 = −10 ,R - матрица ВТФ.Положим1 = 0 0(2)0 = −10 01 = −10 0 0Таким образом, матрицы1и0подобны с ортогональной матрицей.Аналогично, сделаем следующие шаги:1 = 1 1 , 1 = −11 , 1 − ВТФ...

= , = 0, 1, . . .(3)+1 = (4)Понятие о QR-алгоритме. Решение полной проблемы собственных значений.Устремим → ∞,40тогда:⎛× × ...⎜0 × ...⎜ → ⎜ .. .. . .⎝. ..0 0 ...⎞××⎟⎟⎟×⎠×Где на главной диагонали будут стоять собственные значения матриц0 , 1 , . . .(спектры этихматриц совпадают).Заметим, что под главной диагональю могут и не получаться нули в математическом смысле.Достаточно, чтобы значения под главной диагональю были по модулю меньше некоторого числа(т.н. машинный ноль), определяющего точность вычислений. комплексные собственные значения, то в матрице на главной диагонали будут появлятьсяквадраты 2 × 2, она будет иметь вид:⎛⎞×⎜⎟×⎜⎟⎜⎟0 1 → ⎜⎟⎜⎟−10⎝⎠...0Если уПеречислим основные плюсы и минусы QR-алгоритма:1.

(+) Для любой матрицы можно найти весь спектр.2. (-) Во время вычислений нужно держать всю матрицу в памяти.3. (-) Если собственные значения комплексны, то появляются клетки 2го порядка, которыепри последующих итерациях не будут сходиться к 0.Свойства QR-алгоритмаУтверждение. Пусть матрица – ВТФ, а матрица – ВПТФ. Тогда = – ВПТФ.Доказательство. По формуле умножения матриц: =∑︁ .=1Так как– ВТФ, то всепри>равны нулю, так как– ВПТФ, то всепри > +1равны нулю. Модифицируем формулу согласно этим утверждениям: =+1∑︁ .=То есть если i > j + 1, то = 0. А это и значит, что – верхняя почти треугольная матрица.Утверждение.

Пусть матрица – ВПТФ, а матрица – ВТФ. Тогда = – ВПТФ.Доказательство. Доказательство полностью аналогично предыдущему утверждению.Понятие о QR-алгоритме. Решение полной проблемы собственных значений.41Используя данные утверждения, можно значительно ускорить QR-разложение матрицы.QR-алгоритм преобразует матрицу→− 0– ВПТФ:0 = 0 00 = 0 )−11 = 0 0То есть форма матрицы– ВПТФ по доказанному утверждению– ВПТФ по доказанному утверждению ( ∈ N) не ухудшается,2 действий.следовательно, очередная матрица можетбыть выполнена не более чем заЕсли же матрица0- симметричная, то один шаг потребует всегодействий.Глава IIИнтерполирование и приближениефункций§1Постановка задачи интерполирования () – дискретная функция аргумента , ∈ [, ], , ∈ R.

Функция () определена вточках 0 , 1 , . . . , , ∈ N; ≤ 0 < 1 < . . . < ≤ = { }0 – узлах функции. Во всех узлахзаданы значения ( ) = , ∀ = 0, . Требуется найти значение функции () в произвольнойПустьточке.Замечание. В указанной формулировке решений задачи бесконечно много. Для уточнениядополнительно указывают класс функций, которые будут использоваться для построениязначений ()в произвольной точке.Интерполирование алгебраическими полиномамиОпределение. Назовем интерполяционным полиномом Лагранжа функции () по узлам{ }0полином степени: () = 0 + 1 + . .