Интерполяция (матем.)
Интерполяция в математике и статистике, отыскание промежуточных значений величины по некоторым известным её значениям. Например, отыскание значений функции f (x) в точках х, лежащих между точками (узлами И.) x0 < x1 < ... <xn, по известным значениям yi = f (xi) (где i = 0, 1, ..., n). В случае, если х лежит вне интервала, заключённого междуx0 и xn, аналогичная задача наывается задачей экстраполяции. При простейшей линейной И. значение f (x) в точке х, удовлетворяющей неравенствам x0 < x < x1, принимают равным значению
линейной функции, совпадающей с f (x) в точках х = x0 и х = x1. Задача И. со строго математической точки зрения является неопределённой: если про функцию f (x) ничего неизвестно, кроме её значений в точках x0, x1,..., хn, то её значение в точке х, отличной от всех этих точек, остаётся совершенно произвольным. Задача И. приобретает определённый смысл, если функция f (x) и её производные подчинены некоторым неравенствам. Если, например, заданы значения f (x0) и f (x1) и известно, что при x0 < x < x1 выполняется неравенство |f¢’’(x)| £ M, то погрешность формулы (*) может быть оценена при помощи неравенства
Более сложные интерполяционные формулы имеет смысл применять лишь в том случае, если есть уверенность в достаточной "гладкости" функции, т. е. в том, что она обладает достаточным числом не слишком быстро возрастающих производных.
Кроме вычисления значений функций, И. имеет и многочисленные другие приложения (например, при приближённом интегрировании, приближённом решении уравнений, в статистике при сглаживании рядов распределения с целью устранения случайных искажений).
Билет № 12.
1). Ортогональные матрицы вращения, их использование для реализации QR- разложения (преобразования Гивенса).
2). Решение частичной проблемы собственных значений, степенной метод.
Ортогональные матрицы вращения (преобразования Гивенса), их использование для реализации QR-разложения. Пусть iи j— некоторые целые индексы, такие что l ≤ i<j ≤ n,aθ — некоторое вещественное число. Рассмотрим следующую матрицу размерностиn:
(такая матрица отличается отединичной лишь тем, что на пересечениях ее (i, j) строк и столбцов расставлены величины cosθ и sinθ). Проверкой условия: если определяющая линейный оператор матрица Q удовлетворяет соотношению QTQ = Е = I, (то есть ее обратная матрица совпадает с транспонированной)легко можно убедиться, что определяемый матрицей оператор является ортогональным. Пусть имеется некоторый вектор х Rn и его образ х' = х. Очевидно, что они отличаются лишь i-ым и j-ым компонентами, для которых справедливо соотношение (1) На практике обычно возникает задача нахождения такого вращения, которое обнуляло бы один из компонентов хi, или . Обозначим для краткости с = cosθи s = sinθ. Если требуется обнулить xj, то согласно (1) нужно найти такие c и s, чтобы выполнялось cxj — sxi = 0. Добавив к этому уравнению связывающее c и s основное тригонометрическое тождество, получим систему из двух уравнений с двумя неизвестными:
имеющую решение
Для хранения матриц вращения достаточно двух целых (i, j) и двух вещественных (s, с) чисел; процедура матрично-векторного умножения при этом выполняется согласно формулам (1). Свойства:
Замечание: чем больше , тем точнее результат деления, тем точнее оценка матрицы Если cosθ=1 и sinθ=0, то ортогональная матрица становится единичной.
Трудоемкость метода = kn3, где k<1 (зависит от конкретной реализации ≈ n3) Метод Гивенса основан на преобразовании подобия. Алгоритм построен таким образом, что вновь образованные нулевые элементы при всех последующих преобразованиях сохраняются. Его единственный недостаток состоит в том, что симметричная матрица приводится не к диагональному, а к трехдиагональному виду.
В случае матрицы размерности п х п метод Гивенса требует п — 2 основных шагов, на каждом из которых выполняется ряд преобразований, число которых зависит от числа нулей, которое хотят получить в данном столбце или строке. На k -м шаге обращают в нули элементы, стоящие вне трех диагоналей k-й строки и k -го столбца, сохраняя в то же время нулевые элементы, полученные на предыдущих шагах. Таким образом, перед началом k -го шага преобразованная матрица является трехдиагональной, если ограничиться рассмотрением ее первых k — 1 строк и столбцов. По мере преобразований симметричная матрица размерности 5х5 приобретает следующие формы:
На каждом основном шаге изменяются лишь те элементы матрицы аij, которые расположены в ее правой нижней (заштрихованной) части. Ясно, что на каждой следующей стадии выполняется меньшее число преобразований, чем на предыдущей. Всего для приведения матрицы к трехдиагональному виду требуется выполнить (n2 —Зп + 2)/2 преобразований. При выполнении одного шага преобразований можно обратить в нуль сразу все элементы целой строки и столбца, стоящие вне трех диагоналей матрицы. |
Решение частичной проблемы собственных значений. Степенной метод и его модификации. Решение частичной проблемы собственных значений сводится к поиску нескольких собственных значений (наибольших, наименьших) При степенном методе определяется одно наибольшее собственное значение Степенной метод А – λЕ λ1, … λn – собственные значения
- для i-того элемента
Рассмотрим отношение: так как │λ1│это max значение, то с ростом k вес значения в скобках будет стремиться к нулю, поэтому через определенное число итераций получим
Могут возникнуть сложности, если есть несколько равных собственных значений, поэтому существуют различные модификации степенного метода для решения задачи в любом из случаев Оценка погрешности: Если матрица плохо обусловленная, то погрешность задания ее коэффициентов сильно влияет на результат Существуют специальные алгоритмы, использующие разреженные матрицы для вычисления собственных значений
|