main (1160440), страница 8
Текст из файла (страница 8)
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. Интерполирование и приближение функцийИскомые полиномы () можно представить следующим образом: () =(),( − ) ′ ( ) = 0, .(3)Заметим, что условия (2) для полиномов () выполнены.
Учитывая равенства (1) и (3),запишем интерполяционный полином в форме Лагранжа: () =∑︁=0() ( ).( − ) ′ ( )Оценим точность приближения функции () интерполяционным полиномом в формеЛагранжа.Определение. Пусть () — интерполяционный полином в форме Лагранжа для функции (). Тогда функция () = () − ()(4)называется погрешностью интерполирования функции () интерполяционным полиномом ().Пусть существует ( + 1)-ая производная функции () на отрезке [, ]. Тогда () = (+1) ()(),( + 1)!где ∈ [, ].Обычно оценку погрешности аппроксимации (5) записывают в виде⃒⃒+1⃒ (+1) ⃒()⃒.| ()| 6|()| , где +1 = sup ⃒( + 1)!∈[,](5)(6)Замечание 1. Вывод формул (5) и (6) в данном курсе не рассматривается, его можнонайти в [1].Замечание 2. Если исходная функция является полиномом степени, не превышающей, то интерполяционный полином в форме Лагранжа приближает ее точно.1Замечание 3.
Наличие в оценке погрешности (6) быстро убывающего множителя (+1)!вовсе не гарантирует сходимость интерполяционного полинома в форме Лагранжа к заданной функции при увеличении числа узлов в разбиении. Более того, начальное разбиениеможет быть выбрано так, что мы вовсе не получим сходимости. Поэтому на практике лучше разбивать область определения функции на меньшие отрезки, на каждом изкоторых приближать функцию полиномом невысокой степени, и потом «сшивать» полученные приближения в одну функцию, определенную уже на всем отрезке.§3Разделенные разностиРассмотрим вещественную функцию (), ∈ [, ] ⊂ R,заданную в узловых точках произвольного разбиения отрезка [, ]: 6 0 < 1 < 2 < .
. . < 6 , ( ) = , = 0, .§3. Разделенные разности51Определение. Разделенной разностью первого порядка, построенной по несовпадающимузлам и , называется отношение ( , ) = ( ) − ( ), − 0 6 , 6 .(1)Обычно мы будем рассматривать разделенные разности, составленные по соседним узлам.Например, (1 ) − (0 ) (2 ) − (1 ) (0 , 1 ) =, (1 , 2 ) =.1 − 02 − 1Замечание. Отношение (1) является дискретным аналогом первой производной.Определение. Разделенной разностью второго порядка, построенной по несовпадающимузлам 0 , 1 , 2 , называется отношение (0 , 1 , 2 ) = (1 , 2 ) − (0 , 1 ).2 − 0(2)Замечание.
Отношение (2) является дискретным аналогом второй производной.Определение. Пусть даны ( , . . . , + ) и (+1 , . . . , ++1 ) — разделенные разности-ого порядка по соответствующим узлам, где 0 6 , 6 . Тогда разделенной разностью ( + 1)-ого порядка, построенной по несовпадающим узлам , +1 , . . . , ++1 ,называется отношение ( , +1 , . . . , ++1 ) = (+1 , +2 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
