Г.М. Кобельков - Курс лекций по численным методам (1160467), страница 2
Текст из файла (страница 2)
Точнее говоря, в системе F (β, t, L, U ), где β — основание системы, t — количестворазрядов, а L и U — верхний и нижний пределы изменения порядка, число x ∈ F записывается в видеd1d2dt+ 2 + . . . + t βk .(1)x=±βββЗдесь 0 6 di < β (цифры числа), причём d1 > 0, а k ∈ [L, U ]. Очевидно, количество чисел в системе F равно2(β − 1)β t−1 (U − L + 1) + 1.Введём обозначения:• δ — наименьшее положительное число в F .
Очевидно, δ = β L−1 .• λ — наибольшее положительное число в F .• ε — расстояние между 1 и следующим числом в F (так называемое «машинное ε»). Очевидно, ε = β 1−t .1.2. Округление и ошибкиРазберёмся с тем, как происходит округление вещественных чисел. Пусть у нас есть число0.d1 d2 . . . dt dt+1 dt+2 . . . dt+m .(2)Прибавим к нему число 0.0 . . . 0 β2 (ненулевая цифра стоит на позиции t), получим число0.p1 . . . pt pt+1 .
. .(3)Результатом округления будет число 0.p1 . . . pt .Мы хотели вычислить число x, но немного обсчитались и получили какое-то другое число x′ . Как измеритьнашу ошибку?Определение. Абсолютной погрешностью вычислениявеличина ∆(x) := |x− x′ |. Относитель называется x−x′ ной погрешностью вычисления называется число δ(x) := x .Ясно, что абсолютная погрешность куда менее информативна, чем относительная.
Если x ∼ 10100 , и мыошиблись на ±104 , то это не так уж плохо, а вот если x ∼ 104 , то мы, грубо говоря, ничего не вычислили.Замечание. На относительно древних процессорах можно было наблюдать следующее забавное явление,связанное с порядком вычислений:(A + 1) − A 6= A + (1 − A),(4)где A = 240 , β = 2, а t = 40. При этом левая часть выражения могла принимать значения 0 и 2, а правая всегдаравна 1.Но это еще не самое страшное, что в жизни бывает. А ещё бывает потеря значащих цифр.
Пример:-0.123456660.123456650.00000001А что будет после нормализации? Единица переползёт на первую позицию после запятой, получится число0.10000000 · 10−7 . А за ней, естественно, будут нули. Но эти нули там появились совершенно спонтанно, и формально говоря, на их месте могли бы быть любые другие знаки (это были те самые нули, которые до вычитаниянаходились за пределами разрядной сетки). В результате в данном примере точность наших вычислений падаетв 107 раз.Есть и другие интересные примеры того, как ничтожная ошибка в вычислениях может колоссально повлиять20Qна результат.
Рассмотрим многочлен P20 =(x − n). Он, конечно же, имеет 20 вещественных корней. Ноn=1предположим, что мы слегка наврали, вычисляя коэффициент при x19 , и вместо 210 получили 210 + 2−23 .Казалось бы, ерунда. Ан нет: x1 = 1.000 . . . , x2 = 2.000 . . . , а вот десятый и одиннадцатый корни у новогомногочлена уже комплексные, и их мнимая часть весьма далека от нуля: x10,11 = 10.095 ± 0.643i.52. Аппроксимация функций2.1. Интерполяция многочленом Лагранжа2.1.1.
Постановка задачи и оценка её сложностиПусть f : [a, b] → R — некоторая функция, и нам известны её значения в точках x1 < · · · < xn ∈ [a, b]. Задачаинтерполяции состоит в приближении данной функции на отрезке [a, b]. Хорошо известно, что существует ипритом единственный многочлен (Лагранжа) степени n−1, проходящий через заданные n точек и принимающийв них заданные значения.Рассмотрим базисные функцииY x − xi.(1)ϕj (x) :=xj − xii6=jТогда многочлен имеет видLn (x) :=nX(2)f (xj )ϕj (x).j=1Через ωn (x) будем всегда обозначать многочлен такого вида: ωn (x) :=nQj=1(x − xj ).Оценим число операций, необходимых для вычисления многочлена Лагранжа в точке x.
Если делать совсемтупо, будет 4n(n − 1) + n ∼ 4n2 операций. Можно схалтурить, домножив числитель и знаменатель каждой дробиϕj (x) на (x − xj ), тогда числитель можно будет вычислить однократно, тем самым получим 2n2 операций. Аесли вспомнить про запись многочлена в форме Ньютона, то можно ещё немного наэкономить, затратив 32 n2операций.2.1.2.
Оценка погрешности приближения функции многочленом ЛагранжаВезде, где не оговорено противное, норма k·k обозначает обычную равномерную норму в C[a, b].Замечание. Многочлен Лагранжа можно применять для интерполяции только внутри отрезка [a, b]. Пытаться экстраполировать функцию вне отрезка этим многочленом недопустимо!Теорема 2.1. Пусть функция f такова, что f (n) ∈ C[a, b]. Тогда имеет место формула для погрешности:kf − Ln k 6f (n) (ξ)kωn (x)k .n!(3)Рассмотрим разностьϕ(t) := f (t) − Ln (t) − k · ωn (t).(4)Подберём константу k так, что функция ϕ имела бы нуль в некоторой точке x.
А именно, положимk :=f (x) − Ln (x).ωn (x)(5)Тогда функция ϕ(t) будет иметь n + 1 нуль, т. е. точки {x, x1 , . . . , xn }. Значит, по теореме Ролля ϕ′ (t) имеет nнулей, а ϕ(n) (t) имеет хотя бы один нуль — некоторую точку ξx . Дифференцируя формулу для ϕ, получаемϕ(n) (t) = f (n) (t) − k · n!(6)Подставляя значение k, получаемf (n) (ξx )ωn (x).n!Остаётся навестить на эту формулу знак нормы, и заявить, что теорема доказана. f (x) − Ln (x) =(7)Замечание. Мы видим, что качество приближения зависит от функции ωn , а фактически — от выбора узлов.Далее мы узнаем, что если их выбирать особым образом, то можно добиться того, чтобы kf − Ln k → 0 при1n → ∞. Для равномерно распределённых узлов есть функция 1+25x2 , для которой погрешность неограниченновозрастает при n → ∞.
Связано это с тем, что у неё есть полюса ± 5i .62.1.3. Многочлены ЧебышёваДля начала заметим, что существует многочлен со старшим коэффициентом 1, имеющий на заданном отрезкеn корней и обладающий наименьшей равномерной нормой. Действительно, такой многочлен имеет видnYi=1(x − xi ),(8)xi ∈ [a, b],то есть ограничение на нули замкнутое (и даже компактное). Далее, норма на отрезке, очевидно, непрерывнозависит от этих нулей, а потому где-то достигает минимума.Поиском таких многочленов мы сейчас и займёмся. Точнее говоря, искать мы ничего не будем, а просто«с потолка» предъявим ответ и докажем, что это в точности то, что нам нужно. Рассмотрим так называемыемногочлены Чебышева, задаваемые рекуррентным соотношениемT0 (x) := 1,T1 (x) := x,(9)Tn+1 (x) := 2xTn (x) − Tn−1 (x).Они обладают некоторыми очевидными свойствами:1.
deg Tn = n;2. T2n — чётная функция, T2n+1 — нечётная функция (следует из рекуррентной формулы).3. Tn = 2n−1 xn + . . .4. Tn = cos(n arccos x). В самом деле, по известной тригонометрической формуле имеемcos (n + 1) arccos x + cos (n − 1) arccos x = 2x cos(n arccos x).(10)Рекуррентное соотношение (9) позволяет найти явную формулу для Tn . Будем искать решение в виде Tn == µn . Имеемµn+1 − 2xµn + µn−1 = 0,(11)√откуда после сокращения на µn−1 имеем µ1,2 = x ± x2 − 1. Отсюда Tn = C1 µn1 + C2 µn2 .
Из начальных условийT0 (x) = 1, T1 (x) = x получаем систему уравнений на Ci :(C1 + C2 = 1,(12)C1 µ1 + C2 µ2 = x.Очевидно, Ci = 12 , а потомуTn (x) =n n ipp1 hx + x2 − 1 + x − x2 − 1.2(13)Найдем в явном виде нули многочленов Tn . Рассмотрим уравнение cos(n arccos x) = 0. Имеемn arccos x =Отсюда arccos x =π2n+kπn .π+ kπ.2(14)Далее берём косинус левой и правой части, получаем ответ:xk = cos(2k + 1)π.2nТакже легко видеть, что максимумы и минимумы многочлена Tn находятся в точках cos kπ2n .Замечание.
Многочлены Чебышёва образуют ортогональную систему на отрезке [−1, 1] с весом(15)√ 1.1−x2Кроме рекуррентного соотношения, с помощью которого мы определяли многочлены Чебышева, есть ещёодно (читателю предлагается в него либо поверить, либо проверить самостоятельно):√ !√ !33T3n (x) = 4Tn (x)Tn x −Tn x +.(16)22Рассмотрим семейство многочленов со старшим коэффициентом 1:Kn := {Pn = xn + · · · ∈ R[x],7deg Pn = n} .(17)1· Tn обладает минимальной равномернойТеорема 2.2. Среди многочленов из Kn многочлен T n := 2n−1нормой. От противного: пусть нашёлся многочлен P ∈ Kn такой, что kP k < T n . Рассмотрим разность этихмногочленов R := T n − Pn . Имеем deg R < n, так как xn сократится. Заметим, что в точках xk := cos kπnимеем sgn R(xk ) = sgn Tn (xk ), потому что эти точки являются экстремумами многочленов Чебышёва (и потомув них многочлен Чебышёва достигает своей нормы), а норма P строго меньше, значит, при вычитании знак непоменяется.
Теперь заметим, что в этих точках знаки экстремумов чередуются. Значит, есть n + 1 точка, гдеразность R меняет знак, то есть имеет не менее n корней. Но deg R < n, поэтому R ≡ 0. Теорема доказана. А вот графики многочленов Чебышева Tn при n ∈ {1, . . . , 9}:Мы строили многочлены Чебышёва на отрезке [−1, 1]. Однако нам может потребоваться перетащить многочлен Чебышёва на любой другой отрезок. Это можно сделать с помощью линейной замены (x ∈ [−1, 1] иy ∈ [a, b]):2y − (a + b).(18)x=b−aТогда корни нового многочлена получатся такие:yj =a+b b−a(2j − 1)π+cos,22n(19)j = 0, . . . , n − 1.Таким образом, для произвольного отрезка [a, b] мы получаем формулу для оценки погрешности при интерполяции многочленом Лагранжа: (n) nf 1b−akf − Ln kC[a,b] 6· n−1 ·.(20)n!222.2. Тригонометрическая интерполяция2.2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
