Численные методы. Ионкин (2013) (1160444), страница 8
Текст из файла (страница 8)
...⎝ .. .. ..00432 = 2−1 1 2 имеет следующий вид:⎞××⎟⎟×⎟⎟= 2−1 1−1 1 2 .×⎟⎟.. ⎟.⎠× ... × ×Через ( − 2) шага получим матрицу , имеющую ВПТФ:⎛× × × ...⎜× × × . . .⎜⎜0 × × ...⎜−1−1 = −2−3. . . 2−1 1−1 1 2 . . . −3 −2 = ⎜ 0 0 × . . .⎜⎜. . . ...⎝ .. .. ..0 0 0 ...⎞××⎟⎟×⎟⎟.×⎟⎟.. ⎟.⎠× ×××××...Определим матрицу = 1 2 . . . −2 . Покажем, что — ортогональная матрица:−1.
. . 1−1 = (1 2 . . . −2 )−1 = −1 . = (1 2 . . . −2 ) = −2−3. . . 1 = −2Таким образом, произвольную матрицу можно привести к матрице с ВПТФ с помощьюпреобразования подобия, задаваемого ортогональной матрицей : = −1 , = 0 при > + 2.Замечание 1. Преобразование подобия сохраняет спектр матрицы: = , = 1, .Доказательство. Рассмотрим ненулевой собственный вектор матрицы , отвечающийсобственному значению : = , ̸= .Домножим обе части равенства на матрицу −1 слева:−1−1 = .Обозначим = −1 .
Отсюда = . Тогда справедливо равенство−1 = .⏟ ⏞Таким образом, является собственным вектором матрицы , и выполнено требуемоеравенство = . Доказательство в обратную сторону очевидно.Замечание 2. Если — симметрическая матрица, то также является симметрической матрицей: = ⇒ = .Доказательство. = −1 . Запишем и преобразуем выражение для :(︀)︀ = (−1 ) = −1 = = −1 = .44§11Глава 1. Численные методы линейной алгебрыПонятие о QR-алгоритме решения полной проблемы собственных значенийУтверждение. Произвольная матрица ( × ) может быть представлена в виде: = ,(1)где — ортогональная матрица, а — матрица, имеющая верхнюю треугольную форму(ВТФ).Доказательство.
Возьмем вектор = (11 , 21 , . . . , 1 ) — первый столбец матрицы .Рассмотрим вектор = + ‖‖, = (1, 0, . . . , 0) .⏟⏞и построим матрицу1 = − 2 .‖‖2По доказанному выше1 = (−‖‖, 0, 0, . . . , 0) .Тогда матрица 1 = 1 будет иметь следующий вид:⎛× × × ...⎜0 × × ...⎜⎜1 = 1 = ⎜ 0 × × . . .⎜ .. ..
.. . .⎝. . ..0 × × ...⎞××⎟⎟×⎟⎟... ⎟.⎠×(︁)︁(1) (1)(1)Пусть теперь = 22 , 32 , . . . , 2 . По вектору однозначно определяется элементарноеотражение с матрицей (( − 1) × ( − 1)), удовлетворяющей равенству = (−‖‖, 0, . . . , 0) .(︂)︂1 . Тогда матрица 2 = 2 1 имеет следующий вид:Пусть 2 = ⎛× × × ...⎜0 × × ...⎜⎜2 = 2 1 = ⎜ 0 0 × . . .⎜ ..
.. .. . .⎝. . ..0 0 × ...⎞××⎟⎟×⎟⎟... ⎟.⎠×После ( − 1) шага получим матрицу = −1 −2 . . . 2 1 , имеющую ВТФ:⎛× × × ...⎜0 × × ...⎜⎜ = −1 −2 . . . 2 1 = ⎜ 0 0 × . . .⎜ .. .. .. . .⎝. . ..0 0 0 ...⎞××⎟⎟×⎟⎟... ⎟.⎠ק11. Понятие о QR-алгоритме решения полной проблемы собственных значений45Введем матрицу = 1 2 . . . −1 . Покажем, что матрица ортогональная, воспользовавшись свойством ортогональности элементарного отражения:−1−1 = −1.
. . 2−1 1−1 = −1. . . 2 1 = (1 2 . . . −1 ) = .Таким образом, справедливо разложение (1) матрицы . В силу того, что в ходе преобразований на матрицу не накладывались ограничения, разложение справедливо дляпроизвольной матрицы.Замечание. Количество операций, необходимых для вычисления QR-разложения матрицы , зависит от вида матрицы . Для произвольной матрицы количество операцийможно оценить величиной порядка 3 , для матрицы, имеющей ВПТФ, — порядка 2 ,для трехдиагональной матрицы — порядка .Рассмотрим оптимальную версию алгоритма. Приведем матрицу к матрице 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 . . . × ⎟⎜⎟ −→ ⎜ ... . ... ⎟ .→∞ ⎝ ... . ⎠.00. . . Если же матрица имеет комплексную пару собственных значений 0 ± 1 , то ей наглавной диагонали предельной матрицы будет соответствовать клетка размера 2 × 2:Ś⎞⎛×⎟⎜×⎜⎟⎜⎟0 1⎜⎟ −→ ⎜⎟.−1 0⎟→∞ ⎜⎜⎟..⎝⎠.0×46Глава 1. Численные методы линейной алгебрыЗамечание 1. Итерационный процесс останавливается, когда все элементы ниже главной диагонали, либо ниже побочной (в случае комплексно-сопряженных собственных значений) матрицы при некотором становятся равными нулю.
Однако следует заметить, что в данном случае под нулем мы понимаем либо машинный ноль, либо число,меньшее некоторой заданной величины — необходимой точности вычисления.Замечание 2. QR-алгоритм применим к произвольной матрице .Замечание 3. QR-алгоритм является очень затратным по необходимому количествуопераций и объему памяти, используемому для хранения промежуточных матриц.§12Предварительное преобразование матрицы к ВПТФ. Неухудшение ВПТФ при QR-алгоритмеЛемма 1. Пусть = , где имеет ВТФ, а имеет ВПТФ. Тогда имеет ВПТФ.Доказательство. Выпишем элемент матрицы по определению произведения матриц: =∑︁ , , = 1, .=1Учтем, что = 0 при < и = 0 при > + 1: =∑︁= =+1∑︁ , , = 1, .=При > + 1 получим, что = 0.
Таким образом, имеет ВПТФ и лемма доказана.Аналогичным образом доказывается следующая лемма (ее непосредственное доказательство предоставляется читателю).Лемма 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+ .Глава 2Интерполирование и приближениефункций§1Постановка задачи интерполированияРассмотрим некоторый технологический процесс, характеризуемый множеством параметров.
Разместим в среде протекания процесса конечное число датчиков, позволяющих получать точные значения параметров процесса в ограниченном числе точек среды. Для получения исчерпывающей информации о протекании процесса необходимо уметь оцениватьзначения параметров процесса в точках, в которых нет возможности их измерить.Под интерполированием (точное определение будет дано ниже) понимается процесспоиска промежуточных значений величины по имеющемуся дискретному набору известных значений.
В вычислительной математике интерполирование обычно рассматриваетсяв рамках задачи вычисления промежуточных значений функций, например, при вычислении значений специальных функций, являющихся решениями дифференциальных уравнений специального вида (функции Бесселя, Ханкеля и другие). Как правило, значенияфункций такого рода задаются таблицами, шаг которых может оказаться слишком большим для конкретной задачи. В таком случае используют интерполирование для получениязначений функции с заданной точностью.Интерполирование функций используется при исследовании сходимости разностных методов решения дифференциальных задач. При исследовании сходимости необходимо уметьсравнивать сеточные и непрерывные функции. Эту задачу можно решить двумя методами. Первый метод состоит в проецировании непрерывной функции на сетку и последующемсравнении сеточных функций. Второй способ состоит в восстановлении непрерывной функции по сеточной с помощью интерполирования и последующем сравнении непрерывныхфункций.Постановка задачи.
Рассмотрим вещественную функцию (), ∈ [, ] ⊂ Rи произвольным образом заданное разбиение области определения этой функции: 6 0 < 1 < 2 < . . . < 6 .Точки { }=0 называются узловыми точками функции (). В этих точках задано значение функции: ( ) = , = 0, .Задача интерполирования состоит в нахождении значений функции () на всем отрезке[a,b] по ее значениям в узловых точках.48Глава 2. Интерполирование и приближение функцийЗамечание.
Далее будем считать термины «интерполирование функции» и «приближение функции» синонимами.Заметим, что в постановке задачи интерполирования не указан конкретный метод построения приближенных значений функции (). В силу этого задача допускает скольугодно много решений. В этой главе рассматривается задача приближения заданной функции вещественными полиномами: () = 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)Получим систему линейных уравнений с ( + 1)-им уравнением относительно коэффициентов полинома () с матрицей⎛⎞1 0 20 . . . 0⎜1 1 2 . . . ⎟11⎟⎜ = ⎜. ... . ... ⎟ ...⎝. ..
. ⎠.21 . . . Определитель матрицы — это определитель Вандермонда ( + 1)-ого порядка:|| =∏︁( − ).06<6Поскольку все узлы различны, матрица невырождена: || ≠ 0.Из невырожденности матрицы следует существование и единственность решения системы (2). Таким образом, для любой функции () существует интерполяционный полином (), и его коэффициенты однозначно определяются по значениям функции в ( + 1)ой узловой точке.Замечание. Помимо интерполирования иногда решают задачу экстраполирования — прогнозирования поведения функции за пределами отрезка. Задача экстраполирования имеетбольшую погрешность, чем задача интерполирования.§2.
Интерполяционная формула Лагранжа§249Интерполяционная формула ЛагранжаРассмотрим вещественную функцию ∈ [, ] ⊂ R, (),заданную в узловых точках произвольного разбиения отрезка [, ]: 6 0 < 1 < 2 < . . . < 6 , = 0, . ( ) = ,Определение. Интерполяционный полином для функции (), заданный формулой () =∑︁ = 0, , () ( ),(1)=0где () — полином степени , называется интерполяционным полиномом в форме Лагранжа.Из определения интерполяционного полинома следует, что ( ) = ( ) = , = 0, .Из этих равенств следуют условия, = 0, . ( ) = ,(2)Будем искать полиномы () с учетом этих условий.Рассмотрим полином ( + 1)-ой степени вида() =∏︁( − ).=0Вынесем за скобку множитель ( − ):⎛⎞∏︁⎜⎟() = ( − ) ⎝ ( − )⎠ ,=0̸=продифференцируем по :⎛⎜ ′ () = ( − ) ⎝∏︁⎞′⎟ ⎜( − )⎠ + ⎝=0̸=и подставим в полученное выражение = :⎛⎞⎜∏︁⎟ ′ ( ) = ⎝ ( − )⎠ ,=0̸=⎛∏︁⎞⎟( − )⎠=0̸= = 0, .50Глава 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
