main (1160446), страница 8
Текст из файла (страница 8)
. , 2 , где 2 , = 2, элементы второго столбца 1 . Повектору однозначно определяется элементарное отражение с матрицей (( − 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 ...⎞××⎟⎟×⎟⎟... ⎟.⎠×Введем матрицу = 1 2 . . . −1 . Покажем, что матрица ортогональная, воспользовавшись свойством ортогональности элементарного отражения:−1−1 = −1. . . 2−1 1−1 = −1. . .
2 1 = (1 2 . . . −1 ) = .Таким образом, справедливо разложение (1) матрицы . В силу того, что в ходе преобразований на матрицу не накладывались ограничения, разложение справедливо дляпроизвольной матрицы.§11. Понятие о QR-алгоритме решения полной проблемы собственных значений45Число операций, необходимых для вычисления 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 , то ей наглавной диагонали предельной матрицы будет соответствовать клетка размера 2 × 2:⎛⎞×⎜⎟×⎜⎟⎜⎟0 1⎜⎟ −→ ⎜⎟.−10⎟→∞ ⎜⎜⎟..⎝⎠.0×Итерационный процесс останавливается, когда все элементы ниже главной диагонали, либо ниже побочной (в случае комплексно-сопряженных собственных значений) матрицы при некотором становятся равными нулю.
Однако следует заметить, что в данном случае под нулем мы понимаем либо машинный ноль, либо число,меньшее некоторой заданной величины — необходимой точности вычисления.Замечание 1.Замечание 2.QR-алгоритм применим к произвольной матрице .QR-алгоритм является очень затратным по необходимому числу операций и объему памяти, используемому для хранения промежуточных матриц.Замечание 3.46§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+ . Таким образом, если нужно найти все собственные значенияматрицы , сначала приведем ее к ВПТФ, которую обозначим 0 , и для этой матрицы.осуществим QR-алгоритм: = , = , = 0, 1, 2, ...
Так как имеет ВПТФ,+10то все матрицы в QR-алгоритме не ухудшают ВПТФ, а разложения и требуют число действий пропорциональное 2 , а не 3 в случае, если 0 не имеет ВПТФ.Следовательно, все собственные значения будут найдены с меньшими затратами.Глава IIИнтерполирование и приближениефункций§13Постановка задачи интерполированияРассмотрим некоторый технологический процесс, характеризуемый множеством параметров. Разместим в среде протекания процесса конечное число датчиков, позволяющих получать точные значения параметров процесса в ограниченном числе точек среды.
Для получения исчерпывающей информации о протекании процесса необходимо уметь оцениватьзначения параметров процесса в точках, в которых нет возможности их измерить.Под интерполированием (точное определение будет дано ниже) понимается процессвосстановления промежуточных значений функции по имеющемуся дискретному наборуизвестных значений.
В вычислительной математике интерполирование обычно рассматривается в рамках задачи вычисления промежуточных значений функций, например, привычислении значений специальных функций, являющихся решениями дифференциальныхуравнений специального вида (функции Бесселя, Ханкеля и другие). Как правило, значения функций такого рода задаются таблицами, шаг которых может оказаться слишкомбольшим для конкретной задачи. В таком случае используют интерполирование для получения значений функции с заданной точностью.Интерполирование функций используется при исследовании сходимости разностных методов решения дифференциальных задач. При исследовании сходимости необходимо уметьсравнивать сеточные и непрерывные функции. Эту задачу можно решить двумя методами.
Первый метод состоит в проецировании непрерывной функции на сетку и последующемсравнении сеточных функций. Второй способ состоит в восстановлении непрерывной функции по сеточной с помощью интерполирования и последующем сравнении непрерывныхфункций.Постановка задачи.Рассмотрим вещественную функцию (), ∈ [, ] ⊂ Rи заданное разбиение области определения этой функции, удовлетворяющее условиям: 6 0 < 1 < 2 < . . . < 6 .Точки { }=0 называются узловыми точками функции ().
В этих точках задано значение функции: ( ) = , = 0, .48Задача интерполирования состоит в нахождении значений функции () на всем отрезке[, ] по ее значениям в узловых точках.Заметим, что в постановке задачи интерполирования не указан конкретный метод построения приближенных значений функции (). В силу этого задача допускает скольугодно много решений. В этой главе рассматривается задача приближения заданной функции вещественными полиномами: () = 0 + 1 + 2 2 + .
. . + , ∈ R,∑︁2 ̸= 0.=0Вещественный полином -й степени () называется интерполяционным полиномом для функции (), построенным по узлам { }=0 , если его значения вузловых точках совпадают со значениями функции в этих точках:Определение.(1) = 0, . ( ) = ,Для любой функции () существует единственный интерполяционныйполином степени , построенный по ( + 1)-му узлу.Утверждение.Доказательство.Распишем систему (1) покоординатно:⎧⎪0 + 1 0 + 2 20 + . .
. + 0 = 0⎪⎪⎪⎨ + + 2 + . . . + = 01 12 1 11⎪...⎪⎪⎪⎩ + + 2 + . . . + = 01 2 .(2)Получили систему линейных уравнений относительно коэффициентов полинома () сматрицей⎛⎞1 0 20 . . . 0⎜1 1 2 . . . ⎟11⎟⎜ = ⎜. ... . ... ⎟ ...⎝. .. . ⎠.1 2 . . . Определитель матрицы — это определитель Вандермонда ( + 1)-го порядка:|| =∏︁( − ).06<6Поскольку все узлы различны, матрица невырождена: || ≠ 0.Из невырожденности матрицы следует существование и единственность решения системы (2). Таким образом, для любой функции () существует интерполяционный полином (), и его коэффициенты однозначно определяются по значениям функции в заданных узлах.Помимо интерполирования иногда решают задачу экстраполирования — прогнозирования поведения функции за пределами отрезка.
Задача экстраполирования имеетбольшую погрешность, чем задача интерполирования.Замечание.§14. Интерполяционная формула Лагранжа§1449Интерполяционная формула ЛагранжаРассмотрим вещественную функцию ∈ [, ] ⊂ R, (),заданную в узловых точках произвольного разбиения отрезка [, ]: 6 0 < 1 < 2 < . . . < 6 , = 0, . ( ) = ,Определение.Интерполяционный полином для функции (), заданный формулой () =∑︁(1) = 0, , () ( ),=0где () — полином степени , называется интерполяционным полиномом в форме Лагранжа.Из определения интерполяционного полинома следует, что ( ) = ( ) = , = 0, .Из этих равенств следуют условия(2), = 0, . ( ) = ,Будем искать полиномы () с учетом этих условий.Рассмотрим полином ( + 1)-й степени вида() =∏︁( − ).=0Выделим множитель ( − ):⎛⎞∏︁⎜⎟() = ( − ) ⎝ ( − )⎠ ,=0̸=продифференцируем по :⎛⎜ ′ () = ( − ) ⎝∏︁⎞′⎟ ⎜( − )⎠ + ⎝=0̸=и подставим в полученное выражение = :⎛⎞⎜∏︁⎟ ′ ( ) = ⎝ ( − )⎠ ,=0̸=⎛∏︁⎞⎟( − )⎠=0̸= = 0, .50Искомые полиномы () можно представить следующим образом: () =(),( − ) ′ ( ) = 0, .(3)Заметим, что условия (2) для полиномов () выполнены.
Учитывая равенства (1) и (3),запишем интерполяционный полином в форме Лагранжа: () =∑︁=0() ( ).( − ) ′ ( )Оценим точность приближения функции () интерполяционным полиномом в формеЛагранжа.Определение.цияПусть () — интерполяционный полином для функции (). Тогда функ () = () − ()(4)называется погрешностью интерполирования функции () интерполяционным полиномом ().Пусть существует ( + 1)-я производная функции () на отрезке [, ]. Тогда () = (+1) ()(),( + 1)!где ∈ [, ].Обычно оценку погрешности аппроксимации (5) записывают в виде⃒⃒+1⃒ (+1) ⃒()⃒.| ()| 6|()| , где +1 = sup ⃒( + 1)!∈[,]Замечание 1.найти в [1].(5)(6)Вывод формул (5) и (6) в данном курсе не рассматривается, его можноЗамечание 2. Если исходная функция является полиномом степени, не превышающей, то интерполяционный полином приближает ее точно, то есть () ≡ 0.1Наличие в оценке погрешности (6) быстро убывающего множителя (+1)!вовсе не гарантирует сходимость интерполяционного полинома к заданной функции при увеличении числа узлов в разбиении.
Более того, начальное разбиение может быть выбранотак, что мы вовсе не получим сходимости. Поэтому на практике лучше разбивать область определения функции на меньшие отрезки, на каждом из которых приближатьфункцию полиномом невысокой степени, и потом «сшивать» полученные приближенияв одну функцию, определенную уже на всем отрезке.Замечание 3.§15Разделенные разностиРассмотрим вещественную функцию (), ∈ [, ] ⊂ R,заданную в узловых точках произвольного разбиения отрезка [, ]: 6 0 < 1 < 2 < .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
