Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Сходимость и точность интерполирования сплайнами.При обсуждении эффективности численного метода в первую очередь обращаютвнимание на две характеристики:1. Условие сходимости метода (сходимость).Речь идет о минимальных по возможности ограничениях, при которыхприближенное решение задачи стремится к точному решению задачи.Сходимость означает, что данный метод в принципе позволяет найти решениезадачи с любой степенью точности.2.

Скорость сходимости (точность).Это характеристика близости приближенного решения к точному (характеристикаскорости убывания погрешности) при некоторых дополнительных ограничениях.Посмотрим как решаются эти вопросы в теории сплайнов.Итак, на сегменте [a, b] задана функция f (x) и построена сеткаa = x 0 < x1 < x 2 < K < x n = b; hi = x i − x i −1 > 0 .Введем в рассмотрение величинуh = max hi .(85)1≤i ≤nПриведем без доказательства две теоремы.Теорема 1. Пусть f ( x) непрерывна на сегменте [a, b] , тогда для любого ε > 0можно указать δ (ε ) > 0 такое, что при любой сетке, удовлетворяющей условиюh < δ справедливо неравенство(86)f ( x ) − S ( x ) < ε ∀x ∈ [ a , b ] ,- 60 иными словами S h (x) при h → 0 равномерно сходится к непрерывной функции f (x) .Теорема 2.

Пусть f ( x) имеет на сегменте [a , b ] четыре непрерывных производныхи дополнительно удовлетворяет условию f ′′( a ) = f ′′(b) = 0 . Тогда имеют местонеравенства (оценки):f ( x ) − S ( x ) ≤ M 4 h 4 ∀x ∈ [ a, b] ,(87)f ′( x ) − S ′( x ) ≤ M 4 h 3 ∀x ∈ [ a, b] ,(88)f ′′( x ) − S ′′( x ) ≤ M 4 h(89)2∀x ∈ [ a, b] ,M 4 = max f (4) ( x ) .[a ,b](90)§3. Метод наименьших квадратов.Mетод наименьших квадратов был предложен Гауссом и Лежандром в конце XVIII- начале XIX веков в связи с проблемой обработки экспериментальных данных.

Вэтом случае задача построения функции непрерывного аргумента по дискретнойинформации (1), (2) характеризуется двумя особенностями:1. Число точек xi , в которых проводятся измерения, обычно бывает достаточнобольшим.2. Значения функции yi (2) в точках сетки xi (1) определяются приближенно в связис неизбежными ошибками измерения.С учетом этих обстоятельств строить функцию y ( x ) в виде суммы большого числаслагаемых (3) и добиваться ее точного равенства в точках сетки величинам yi , как этоделалось при интерполировании, становится нецелесообразным.В методе наименьших квадратов аппроксимирующая функция y ( x ) ищется в видесуммы, аналогичной (3), но содержащей сравнительно небольшое число слагаемыхmF ( x ) = ∑ akϕ k ( x ), m < n ,(91)k =0в частности, возможен вариант m n .Предположим, что мы каким-то образом выбрали коэффициенты ak , тогда в каждойточке сетки xi , можно подсчитать погрешностьmδ i = yi − F ( xi ) = yi − ∑ akϕ k ( xi ), i = 0,1,2 ,K ,n .(92)k =0Сумма квадратов этих величин называется суммарной квадратичной погрешностьюnnmJ = ∑δ i 2 = ∑ ( yi − ∑ akϕ k ( xi )) 2 .i =0i =0k =0(93)Она дает количественную оценку того, насколько близки значения функции F ( x )(91) в точках сетки к величинам yi .Меняя значения коэффициентов ak , мы будем менять погрешность J , котораяявляется их функцией.

В результате естественно возникает задача:Найти такой, набор коэффициентов ak , при которых суммарная квадратичнаяпогрешность J оказывается минимальной.- 61 Функцию F ( x ) (91) с набором коэффициентов, удовлетворяющих этомутребованию, называют наилучшим приближением по методу наименьших квадратов.Построение наилучшего приближения сводится к классической задачематематического анализа об экстремуме функции нескольких переменных. Методрешения этой задачи известен. Необходимым условием экстремума являетсяравенство нулю в экстремальном точке всех первых частных производныхрассматриваемой функции. В случае (93) это даетnm∂J= −2∑ ( yi − ∑ akϕ k ( xi ))ϕ l ( xi ) = 0 l = 0,1,K, m .(94)∂ali =0k =0Оставим члены, содержащие ak , слева и поменяем в них порядок суммирования поиндексам i и k . Члены, содержащие yi , перенесем направо. В результате уравнения(94) примут видm∑γk =0lkak = bl , l = 0,1,K ,m ,(95)гдеnγ lk = ∑ϕ l ( xi )ϕ k ( xi ) ,(96)i =0nbl = ∑ϕ l ( xi ) yi .(97)i =0Мы получили систему линейных алгебраических уравнений (95), в которой рольнеизвестных играют искомые коэффициенты разложения a0 , a1 ,K , am .

Числоуравнении и число неизвестных в этой системе совпадает и равно m + 1 . Матрицакоэффициентов системы Г состоит из элементов γ lk , которые определяются формулой(96). Ее называют матрицей Грама для системы функций ϕ 0 ( x ), ϕ1 ( x ),K , ϕ m ( x ) на сетке(1). Отметим, что матрица Грама является симметричной: для ее элементов, согласно(96), справедливо равенство γ lk = γ kl . Числа bl , стоящие в правой части уравнений (95),вычисляются по формуле (97) через значения yi сеточной функции (2).Предположим, что функции ϕ 0 ( x ), ϕ1 ( x ),K , ϕ m ( x ) выбраны такими, чтоопределитель матрицы Грама, отличен от нуля:∆ = det Г ≠ 0 .(98)В этом случае при любой правой части система (95) имеет единственное решение(99)a0 , a1 ,K , am .Рассмотрим наряду с набором коэффициентов (99), полученных в результатерешения системы (95), любой другой набор коэффициентов a0 , a1 ,K , am . Представимчисла ak в видеa0 = a0 + ∆a0 , a1 = a1 + ∆a1 ,K , am = am + ∆am ,(100)222( ∆a0 ) + ( ∆a1 ) + L + ( ∆am ) > 0и сравним значения суммарной квадратичной погрешности J для функций F ( x ) (91),построенных с помощью коэффициентов (99) и (100).- 62 Квадрат погрешности и точке x = xi для функции F ( x ) (91) с коэффициентами (100)можно записать в виде2m⎧⎫δ i = ⎨ yi − ∑ ( ak + ∆ak ) ϕ k ( xi ) ⎬ =k =0⎩⎭222mm⎧⎛⎫ ⎛⎞ m⎞= ⎨⎜ yi − ∑ akϕ k ( xi ) ⎟ − ∑ ∆akϕ k ( xi ) ⎬ = ⎜ yi − ∑ akϕ k ( xi ) ⎟ −k =0k =0⎠ k =0⎠⎩⎝⎭ ⎝(101)2m⎛⎞⎛ m⎞ ⎛ m⎞− 2 ⎜ yi − ∑ akϕ k ( xi ) ⎟ ⎜ ∑ ∆alϕ l ( xi ) ⎟ + ⎜ ∑ ∆akϕ k ( xi ) ⎟ .k =0⎝⎠ ⎝ l =0⎠ ⎝ k =0⎠Здесь в среднем слагаемом мы заменили в одной из сумм индекс суммирования k наl , чтобы не использовать один и тот же индекс в двух разных суммах и иметьвозможность перемножить их почленно.Чтобы получить суммарную квадратичную погрешность, нужно просуммироватьвыражения (101) для δ i2 по индексу i Первые слагаемые не содержат ∆ak .

Их суммадает погрешность J , вычисленную для функции (91) с коэффициентами (99) ak .Рассмотрим теперь сумму вторых слагаемых, которые зависят от ∆al линейно:nm⎧⎛⎞ ⎛ m⎞⎫− 2∑ ⎨⎜ yi − ∑ akϕ k ( xi ) ⎟ ⋅ ⎜ ∑ ∆alϕ l ( xi ) ⎟ ⎬ =i =0 ⎩ ⎝k =0⎠ ⎝ l =0⎠⎭mn⎧ n⎫= −2∑ ∆al ⎨ ∑ yiϕ l ( xi ) − ∑ ak ∑ ϕ k ( xi )ϕ l ( xi ) ⎬ =l =0k =0i =0⎩ i =0⎭mmml =0k =0(102)= −2∑ ∆al {bl − ∑ ak γ lk } = 0.Здесь мы поменяли местами порядок суммирования и воспользовались тем, чтокоэффициенты ak , удовлетворяют системе уравнений (95).С учетом (102) будем иметьJ ( a0 + ∆a0 , a1 + ∆a1 ,K, am + ∆am ) =2(103)⎛ m⎞= J ( a0 , a1 ,K, am ) + ∑ ⎜ ∑ ∆akϕ k ( xi ) ⎟ > J ( a0 , a1 ,K, am ) .i = 0 ⎝ k =0⎠Формула (103) показывает, что функция F ( x ) (91) с коэффициентами ak (100),полученными в результате решения уравнений (95), действительно минимизируетсуммарную квадратичную погрешность J .

Если мы возьмем любой другой наборкоэффициентов (100), отличный от (99), то согласно формуле (103) к погрешностиy ( a0 , a1 ,K , am ) добавится положительное слагаемое и она увеличится.Итак, чтобы построить наилучшее приближение (91) сеточной функции (1), (2) пометоду наименьших квадратов, нужно взять в качестве коэффициентов разложения akрешение системы линейных уравнений (95).n- 63 Задача 7Сеточная функция задана таблицей 1.Таблица 1:xiyii00,00,9510,51,5421,02,0431,52,4642,02,95Построить линейную функцию(104)F ( x ) = a0 + a1 x ,которая дает для нее наилучшее приближение по методу наименьших квадратов.В рассматриваемом случае имеем:n = 4, m = 1, ϕ 0 ( x ) = 1, ϕ1 ( x ) = x .Для определения коэффициентов a0 и a1 составим систему уравнений (95).

Элементыγ lk (l = 0,1, k = 0,1) матрицы Грама вычисляются по формуле (96)4γ 0,0 = ∑ϕ 0 ( xi )ϕ 0 ( xi ) = 5 ,i =04γ 0,1 = γ 1,0 = ∑ϕ 0 ( xi )ϕ1 ( xi ) = 5 ,i =04γ 1,1 = ∑ϕ1 ( xi ).ϕ1 ( xi ) = 7.5 .i =0Числа b0 и b1 , стоящие в правой части уравнений (95), находим по формуле (97)4b0 = ∑ϕ 0 ( xi ) yi = 9,94 ,i =04b1 = ∑ϕ1 ( xi ) yi = 12, 40 .i =0В результате система (95) принимает в рассматриваемом случае вид5a0 + 5a1 = 9.94(105)5a0 + 7,5a1 = 12.40.Определитель системы (105) ∆ = 12,5 ≠ 0 , так что система имеет единственноерешениеa0 = 1,004, a1 = 0,984 .В результате мы получаем следующую линейную аппроксимацию рассматриваемойтабличной функции(106)F ( x ) = 1,004 + 0,984 x .- 64 Теперь, когда функция (106) построена, можно подсчитать погрешностьаппроксимации в точках сетки:δ i = yi − (1,004 + 0,984 xi ) , i = 0,1, 2,3, 4 .В результате получаем(107)δ 0 = −0,054, δ 1 = −0,044, δ 2 = 0,052, δ 3 = −0,020, δ 4 = −0,022 .Отметим, что наибольшая по модулю погрешность достигается в точке x0 = 0 :δ 0 = 0.054 > δ i , i = 1, 2,3, 4 .В заключение сделаем важное замечание.

Характеристики

Список файлов лекций