Н.И. Ионкин - Численные методы, страница 8

⎟.⎠×××0...Через ( − 2) шага получим матрицу , имеющую ВПТФ:⎛× × ×⎜× × ×⎜⎜0 × ×⎜−1 −1−1−1 = −2 −3 . . . 2 1 1 2 . . . −3 −2 = ⎜ 0 0 ×⎜⎜. . .⎝ .. .. ..000...............××××...⎞××⎟⎟×⎟⎟.×⎟⎟.. ⎟.⎠... × ×Определим матрицу = 1 2 . . . −2 . Покажем, что — ортогональнаяматрица:−1. . . 1−1 = = (1 2 .

. . −2 ) = −2−3. . . 1 = −2= (1 2 . . . −2 )−1 = −1 .Это значит, произвольную матрицу можно привести к матрице с ВПТФс помощью преобразования подобия, задаваемого ортогональной матрицей: = −1 , = 0 при > + 2.Замечание 1., = 1, .Преобразование подобия сохраняет спектр матрицы: =Рассмотрим ненулевой собственный вектор матрицы, отвечающий собственному значению :Доказательство. = , ̸= .Домножим обе части равенства на матрицу −1 слева:−1−1 = .§11. Понятие о QR-алгоритме решения полной проблемы собственных значений59Обозначим = −1 . Отсюда = . Тогда справедливо равенство−1 = .⏟ ⏞Таким образом, является собственным вектором матрицы , и выполненотребуемое равенство = . Доказательство в обратную сторону очевидно.Если — симметрическая матрица, то также являетсясимметрической матрицей:Замечание 2.

= ⇒ = .Доказательство. = −1 . Запишем и преобразуем выражение для :(︀)︀ = (−1 ) = −1 = = −1 = .Замечание 3. Симметричная матрица, имеющая верхнюю почти треугольную форму, является симметричной трехдиагональной матрицей.§11Понятие о QR-алгоритме решения полной проблемы собственных значенийУтверждение.лена в виде:Произвольная матрица ( × ) может быть представ(1) = ,где — ортогональная матрица, а — матрица, имеющая верхнюю треугольную форму (ВТФ).Возьмем вектор = (11 , 21 , . . . , 1 ) — первый столбецматрицы .

Рассмотрим векторДоказательство. = + ‖‖, = (1, 0, . . . , 0)⏟⏞и построим матрицу1 = − 2 .‖‖260Глава I . Численные методы линейной алгебрыПо доказанному выше1 = (−‖‖, 0, 0, . . . , 0) .Тогда матрица 1 = 1 будет иметь⎛×⎜0⎜⎜1 = 1 = ⎜ 0⎜ ..⎝.следующий вид:⎞× × ... ×× × . . . ×⎟⎟× × . . . ×⎟⎟... .. . ... ⎟. .⎠. .0 × × ... ×)︁(1) (1)(1)(1)Пусть теперь = 22 , 32 , .

. . , 2 , где 2 , = 2, элементы второгостолбца 1 . По вектору однозначно определяется элементарное отражениес матрицей (( − 1) × ( − 1)), удовлетворяющей равенству(︁ = (−‖‖, 0, . . . , 0) .Пусть 2 =(︂1 )︂. Тогда матрица 2 = 2 1 имеет следующий вид:⎛× × × ...⎜0 × × ...⎜⎜2 = 2 1 = ⎜ 0 0 × . . .⎜ .. .. .. . .⎝. . ..0 0 × ...После ( − 1)-го шага получим матрицу =щую ВТФ:⎛×⎜0⎜⎜ = −1 −2 . . . 2 1 = ⎜ 0⎜ ..⎝.0⎞××⎟⎟×⎟⎟... ⎟.⎠×−1 −2 . .

. 2 1 , имею× × ...× × ...0 × ..... .. . ... .0 0 ...⎞××⎟⎟×⎟⎟... ⎟.⎠×Введем матрицу = 1 2 . . . −1 . Покажем, что матрица ортогональная, воспользовавшись свойством ортогональности элементарного отражения:−1−1 = −1. . . 2−1 1−1 = −1. . . 2 1 = (1 2 . . . −1 ) = .Таким образом, справедливо разложение (1) матрицы . В силу того, что входе преобразований на матрицу не накладывались ограничения, разложение справедливо для произвольной матрицы.§11. Понятие о QR-алгоритме решения полной проблемы собственных значений61Замечание. Число операций, необходимых для вычисления QR-разложенияматрицы , зависит от вида матрицы . Для произвольной матрицы число операций можно оценить величиной порядка 3 , для матрицы с ВПТФ, —порядка 2 , для трехдиагональной матрицы — порядка .Рассмотрим оптимальную версию QR-алгоритма. Приведем матрицу кматрице 0 , имеющей ВПТФ, и осуществим QR-разложение матрицы 0 :0 = 0 0 ,где 0 — ортогональная, а 0 — верхнетреугольная матрица.

Построим матрицу1 = 0 0 .Покажем, что спектры матриц 0 и 1 совпадают. Из вида матриц 0 и 1получим0 = −10 0 ,1 = −10 0 0 .Матрица 1 подобна матрице 0 , и из этого следует, что спектры матрицравны.На следующем шаге осуществим QR-разложение матрицы 1 = 1 1 ипостроим матрицу 2 = 1 1 . Аналогичным образом продолжая вычисления, на -м шаге осуществим QR-разложение матрицы = и построим+1 = . Справедливо следующее утверждение, которое мы приводимбез доказательства ввиду его сложности. Доказательство можно посмотретьв [9] и [10].Если все собственные значения матрицы вещественны,то последовательность матриц { } сходится к матрице, имеющей ВТФ:Утверждение.⎛⎞1 × . . .

×⎜ 0 2 . . . × ⎟⎟⎜ −→ ⎜ ... . ... ⎟ ..→∞ ⎝ .. . ⎠.0 0 . . . Если же матрица имеет комплексную пару собственных значений 0 ± 1 ,то ей на главной диагонали предельной матрицы будет соответствовать62Глава I . Численные методы линейной алгебрыклетка размера 2 × 2:⎛×⎜×⎜⎜0 1⎜ −→ ⎜−1 0→∞ ⎜⎜⎝0‘⎞..⎟⎟⎟⎟⎟.⎟⎟⎠.×Итерационный процесс останавливается, когда все элементы ниже главной диагонали, либо ниже побочной (в случае комплексносопряженных собственных значений) матрицы при некотором становятся равными нулю.

Однако следует заметить, что в данном случае поднулем мы понимаем либо машинный ноль, либо число, меньшее некоторойзаданной величины — необходимой точности вычисления.Замечание 1.Замечание 2.QR-алгоритм применим к произвольной матрице .QR-алгоритм является очень затратным по необходимомучислу операций и объему памяти, используемому для хранения промежуточных матриц.Замечание 3.§12Предварительное преобразование матрицы кВПТФ.

Неухудшение ВПТФ при QR-алгоритмеПусть = , где имеет ВТФ, а имеет ВПТФ. Тогда имеет ВПТФ.Лемма 1.Доказательство.дения матриц:Выпишем элемент матрицы по определению произве- =∑︁ , , = 1, .=1Учтем, что = 0 при < и = 0 при > + 1: =∑︁= =+1∑︁ , , = 1, .=При > + 1 получим, что = 0.

Таким образом, имеет ВПТФ и леммадоказана.§12. Предварительное преобразование матрицы кВПТФ63Аналогичным образом доказывается следующая лемма (ее непосредственное доказательство предоставляется читателю).Лемма 2.Пусть = , где — матрица с ВПТФ, а — матрица сВТФ. Тогда — матрица с ВПТФ.Рассмотрим применение QR-алгоритма для матрицы .

Приведем матрицу к верхней почти треугольной матрице 0 . Запишем QR-разложениематрицы 0 :0 = 0 0 .Поскольку 0 и 0−1 — матрицы, имеющие ВТФ, то матрица 0 , определяемая выражением0 = 0 0−1 ,в силу леммы 2 имеет ВПТФ. Матрица 1 = 0 0 в силу леммы 1 такжеимеет ВПТФ. Таким образом, леммы 1 и 2 гарантируют на каждом шагеQR-алгоритма неухудшение ВПТФ матрицы , ∈ Z+ . Таким образом,если нужно найти все собственные значения матрицы , сначала приведемее к ВПТФ, которую обозначим 0 , и для этой матрицы осуществим QR.алгоритм: = , = , = 0, 1, 2, ...

Так как имеет ВПТФ,+10то все матрицы в QR-алгоритме не ухудшают ВПТФ, а разложения и требуют число действий пропорциональное 2 , а не 3 в случае, если 0 не имеет ВПТФ. Следовательно, все собственные значения будутнайдены с меньшими затратами.Глава IIИнтерполирование иприближение функций§1Постановка задачи интерполированияРассмотрим некоторый технологический процесс, характеризуемый множеством параметров. Разместим в среде протекания процесса конечное числодатчиков, позволяющих получать точные значения параметров процесса вограниченном числе точек среды. Для получения исчерпывающей информации о протекании процесса необходимо уметь оценивать значения параметровпроцесса в точках, в которых нет возможности их измерить.Под интерполированием (точное определение будет дано ниже) понимается процесс восстановления промежуточных значений функции по имеющемуся дискретному набору известных значений.

В вычислительной математике интерполирование обычно рассматривается в рамках задачи вычисления промежуточных значений функций, например, при вычислении значенийспециальных функций, являющихся решениями дифференциальных уравнений специального вида (функции Бесселя, Ханкеля и другие). Как правило,значения функций такого рода задаются таблицами, шаг которых может оказаться слишком большим для конкретной задачи.

В таком случае используютинтерполирование для получения значений функции с заданной точностью.Интерполирование функций используется при исследовании сходимостиразностных методов решения дифференциальных задач. При исследованиисходимости необходимо уметь сравнивать сеточные и непрерывные функции.Эту задачу можно решить двумя методами.

Первый метод состоит в проецировании непрерывной функции на сетку и последующем сравнении сеточныхфункций. Второй способ состоит в восстановлении непрерывной функции по§1. Постановка задачи интерполирования65сеточной с помощью интерполирования и последующем сравнении непрерывных функций.Постановка задачи.Рассмотрим вещественную функцию (), ∈ [, ] ⊂ Rи заданное разбиение области определения этой функции, удовлетворяющееусловиям: 6 0 < 1 < 2 < . .

. < 6 .Точки { }=0 называются узловыми точками функции (). В этих точкахзадано значение функции: ( ) = , = 0, .Задача интерполирования состоит в нахождении значений функции ()на всем отрезке [, ] по ее значениям в узловых точках.Заметим, что в постановке задачи интерполирования не указан конкретный метод построения приближенных значений функции (). В силу этогозадача допускает сколь угодно много решений.

В этой главе рассматриваетсязадача приближения заданной функции вещественными полиномами: () = 0 + 1 + 2 2 + . . . + , ∈ R,∑︁2 ̸= 0.=0Вещественный полином -й степени () называется интерполяционным полиномом для функции (), построенным по узлам{ }=0 , если его значения в узловых точках совпадают со значениями функции в этих точках: ( ) = , = 0, .(1)Определение.Для любой функции () существует единственный интерполяционный полином степени , построенный по ( + 1)-му узлу.Утверждение.Доказательство.Распишем систему (1) покоординатно:⎧⎪0 + 1 0 + 2 20 + . . . + 0 = 0⎪⎪⎪⎨ + + 2 + . . . + = 01 12 1 11.⎪. . .⎪⎪⎪⎩ + + 2 + . . . + = 01 2 (2)66Глава II .

Интерполирование и приближение функцийПолучили систему линейных уравнений относительно коэффициентов полинома () с матрицей⎛⎞1 0 20 . . . 0⎜1 1 2 . . . ⎟11⎟⎜ = ⎜. ... . ... ⎟ ...⎝. .. . ⎠.21 . . . Определитель матрицы — это определитель Вандермонда ( + 1)-го порядка:∏︁|| =( − ).06<6Поскольку все узлы различны, матрица невырождена: || ≠ 0.Из невырожденности матрицы следует существование и единственностьрешения системы (2). Таким образом, для любой функции () существуетинтерполяционный полином (), и его коэффициенты однозначно определяются по значениям функции в заданных узлах.Помимо интерполирования иногда решают задачу экстраполирования — прогнозирования поведения функции за пределами отрезка. Задача экстраполирования имеет большую погрешность, чем задача интерполирования.Замечание.§2Интерполяционная формула ЛагранжаРассмотрим вещественную функцию (), ∈ [, ] ⊂ R,заданную в узловых точках произвольного разбиения отрезка [, ]: 6 0 < 1 < 2 < .

. . < 6 , ( ) = ,Определение.формулой = 0, .Интерполяционный полином для функции (), заданный () =∑︁ () ( ), = 0, ,(1)=0где () — полином степени , называется интерполяционным полиномомв форме Лагранжа.§2. Интерполяционная формула Лагранжа67Из определения интерполяционного полинома следует, что = 0, . ( ) = ( ) = ,Из этих равенств следуют условия ( ) = ,(2), = 0, .Будем искать полиномы () с учетом этих условий.Рассмотрим полином ( + 1)-й степени вида() =∏︁( − ).=0Выделим множитель ( − ):⎛⎜() = ( − ) ⎝∏︁⎞⎟( − )⎠ ,=0̸=продифференцируем по :⎛⎜ ′ () = ( − ) ⎝∏︁⎞′⎛⎟ ⎜( − )⎠ + ⎝=0̸=и подставим в полученное выражение = :⎞⎛⎟⎜∏︁ ′ ( ) = ⎝ ( − )⎠ ,∏︁⎞⎟( − )⎠=0̸= = 0, .=0̸=Искомые полиномы () можно представить следующим образом: () =(),( − ) ′ ( ) = 0, .(3)Заметим, что условия (2) для полиномов () выполнены.