Среднеквадратичные приближения функций
Содержание:
Введение......................
§1. СРЕДНЕКВАДРАТИЧНЫЕ ПРИБЛИЖЕНИЯ……………………...4
1.1. Наилучшее приближение...................
1.2. Линейная аппроксимация.................
1.3. Суммирование рядов Фурье.........................
1.4. Метод наименьших квадратов.....................
§2. Приближение функций, заданных
таблицей, тригонометрическими многочленами
по методу наименьших квадратов.....................
§3. Реализация и тестирование метода наименьших квадратов.
3.1. Описание программы............
3.2. Тестирование программы........
Заключение....................
Литература....................
Текст программы.....................
Введение
Сложные вычислительные задачи, возникающие при исследовании физических и технических проблем, можно разбить на ряд элементарных - таких как вычисление интеграла, решение дифференциального уравнения и т. п. Многие элементарные задачи являются несложными и хорошо изучены. Для этих задач уже разработаны методы численного решения, и нередко имеются стандартные программы решения их на ЭВМ. Есть и достаточно сложные элементарные задачи; методы решения таких задач сейчас интенсивно разрабатываются (например, решение уравнений бесстолкновительной плазмы).
Численные методы являются одним из мощных математических средств решения задачи. Простейшие численные методы мы используем всюду, например, извлекая квадратный корень на листке бумаги. Есть задачи, где без достаточно сложных численных методов не удалось бы получить ответа; классический пример—открытие Нептуна по аномалиям движения Урана.
В современной физике таких задач много. Более того, часто требуется выполнить огромное число действий за короткое время, иначе ответ будет не нужен. Например, суточный прогноз погоды должен быть вычислен за несколько часов; коррекцию траектории ракеты надо рассчитать за несколько минут'(напомним, что для расчета орбиты Нептуна Леверье потребовалось полгода); режим работы прокатного стана должен исправляться за секунды. Это немыслимо без мощных ЭВМ, выполняющих тысячи или даже миллионы операций в секунду.
§1. СРЕДНЕКВАДРАТИЧНЫЕ ПРИБЛИЖЕНИЯ
В данной теме будут рассмотрены вопросы приближения функций f(х), принадлежащих к некоторому классу R, функциями φ(x) из более узкого класса , но за меру близости будет приниматься величина
или
где р(х) — заданная неотрицательная функция, называемая весом. Такое понятие близости имеет смысл по следующим причинам:
1. Во многих случаях
нет никакой необходимости
2. Очень часто приближаемая функция f(х) задана лишь таблицей ее значений, причем последние получены из эксперимента, т.е. имеют случайные погрешности. Если в процессе решения задачи требуется находить значения f(x) для промежуточных значений или иметь аналитическое представление функции f(х), то нецелесообразно прибегать к интерполированию, так как совсем не естественно требовать точного совпадения приближающей и приближаемой функций в некоторых точках, так как значения самой приближаемой функции неточны. Практика показывает, что приближающие функции, построенные по методу среднеквадратичного приближения, значительно лучше представляют реальную функцию f(x), чем интерполяционные многочлены.
3. Так определенная мера близости позволяет расширить класс R приближаемых функций. При рассмотрении равномерного приближения мы ограничивались классом С непрерывных функций, и это было существенное требование, если ставить задачу равномерного приближения функции f(x) многочленами с любой заданной точностью. Здесь же требование непрерывности излишне. Нужно лишь требовать существования , г. е. можно рассматривать приближение функций из класса функций, интегрируемых с квадратом с весом p(x).
1. 1. Наилучшее приближение
Интерполяция позволяет легко аппроксимировать функцию у(x). Однако точность такой аппроксимации гарантирована лишь в небольшом интервале порядка нескольких шагов сетки. Для другого интервала приходится заново вычислять коэффициенты интерполяционной формулы. Нам же всегда желательно иметь единую приближенную формулу , пригодную для большого отрезка . Поэтому далее будем сравнивать заданную и аппроксимирующую функции на большом отрезке.
При интерполяции мы приравниваем значения у(x) и φ(x) в узлах. Если определены неточно - например, из эксперимента, - то точное приравнивание неразумно. Поэтому нередко целесообразней приближать функцию не по точкам, а в среднем, т. е. в норме Lp.
Пусть заданы функция у(х) и множество функций φ(x), принадлежащие линейному нормированному пространству функций. Нас интересуют две задачи. Первая — аппроксимация с заданной точностью: по заданному найти такую φ(x), чтобы выполнялось неравенство . Второе — нахождение наилучшего приближения, т. е. функции , удовлетворяющей соотношению
Существует ли наилучшее приближение и единственно ли оно (для данных функции и множества)? Это имеет место не при любом выборе пространства и множества. Например, в пространстве , выберем функцию у(х) = 1 и множество φ(x)= cx; тогда
В самом деле, при эта норма равна площади заштрихованной трапеции на рис. 1, а, т. е. двум. При |c|>1 эта норма, согласно рис. 1, б, равна площади заштрихованной трапеции (которая опять равна двум) плюс площади заштрихованных треугольников. Значит, для любого c, по модулю меньшего единицы, φ=cx минимизирует норму отклонения, т. е. наилучшее приближение здесь существует, но оно не единственно.
Рис. 1.
Выведем достаточное условие существования наилучшего приближения. Пусть в линейном пространстве функций выбрано множество, образованное функциями вида
где функции можно считать линейно-независимыми. Это множество есть линейное подпространство нашего пространства. Изменим один из коэффициентов суммы (2) на величину ; получим
т. е. норма непрерывно зависит от aк.Очевидно, также есть непрерывная функция коэффициентов ak..
Рассмотрим нормы как функции координат ак. Сфера
есть замкнутое ограниченное множество, поэтому на этой сфере имеет точную нижнюю грань и в силу непрерывности достигает ее при некотором . Очевидно, >0; в противном случае , что противоречит линейной независимости .
Возьмем шар , где какое-то положительное число. В силу однородности нормы функции вне этого шара и, следовательно, . Значит, вне этого шара норма погрешности заведомо далека от нижней грани. Только внутри шара у(х) и достаточно близки по норме. Но шар - ограниченное и замкнутое множество значений координат ak, поэтому непрерывная функция координат достигает на нем точной нижней грани.
Следовательно, в любом линейном нормированном пространстве при линейной аппроксимации (2) наилучшее приближение существует, хотя не во всяком линейном пространстве оно единственно.
На практике используются пространства L2 и С. Рассмотрим приближения в пространстве L2, т. е. среднеквадратичную аппроксимацию.
1.2. Линейная аппроксимация.
Рассмотрим гильбертово пространство действительных функций, интегрируемых с квадратом с весом >0 на [a, b]. Норма в нем равна где скалярное произведение определено следующим образом:
Выберем в качестве аппроксимирующей функции линейную комбинацию (2). Подставляя ее в условие наилучшего приближения (1), получим
Приравнивая нулю производные по коэффициентам, получим систему линейных уравнений
Её определитель есть определитель Грама функций ; поскольку функции линейно-независимы, он отличен от нуля. Следовательно, наилучшее среднеквадратичное приближение существует и единственно. Для его вычисления необходимо решить систему линейных уравнений (3).
Линейно-независимую систему функций можно ортогонализировать. Пусть уже образуют ортонормированную систему, т. е. ; тогда формулы (3) резко упрощаются и становятся удобными для вычислений
Это коэффициенты Фурье, так что наилучшее приближение есть отрезок обобщенного ряда Фурье.
Если функции образуют полную ортонормированную систему, то в силу равенства Парсеваля
Значит, при норма погрешности неограниченно убывает, т. е. наилучшее приближение среднеквадратично сходится к у(x), и возможна аппроксимация с любой точностью.
Отметим, что если не ортогональны, то при определитель Грама обычно быстро стремится к нулю, система (3) становится плохо обусловленной, т. е. ее решение связано с большой потерей точности, и больше 5 — 6 членов суммы (2) брать нецелесообразно. Численная ортогонализация базиса при этом тоже приводит к большой потере точности. Поэтому если нужно большое число членов, то надо или проводить ортогонализацию точно (аналитически), или пользоваться готовыми системами ортогональных функций.
При интерполяции мы обычно полагали . Для среднеквадратичной аппроксимации удобнее в качестве брать многочлены, ортогональные с заданным весом. Наиболее употребительны из них многочлены Якоби (частным случаем которых являются многочлены Лежандра и Чебышева), Лагерра и Эрмита. Для аппроксимации периодических функций используют тригонометрический ряд; он соответствует .
Все перечисленные выше системы функций полные, так что наилучшие приближения по ним среднеквадратично сходятся при , если у(х) интегрируема с квадратом с заданным весом. При более сильных ограничениях имеет место сходимость во всех точках и даже равномерная сходимость.
Замечание 1. Сходимость не во всех случаях может быть равномерной. Более того, не существует такого веса , чтобы любая непрерывная функция у(х) разлагалась в равномерно сходящийся ряд по полиномам, ортогональным с этим весом. Дю Буа-Реймондом и Л. Фейером были построены примеры периодических непрерывных функций, у которых тригонометрический ряд Фурье в отдельных точках расходится.
Замечание 2. Сходимость среднеквадратичного приближения тем лучше, чем меньше у функции у(х) особенностей - разрывов ее самой или ее производных. Если можно выделить основные особенности в виде несложной функции у0(x) и аппроксимировать разность у(x) - у0(x), точность аппроксимации существенно улучшается.
Например, периодически продолжим функцию, изображенную сплошной линией на рис. 2, и аппроксимируем ее тригонометрическим рядом Фурье. Этот ряд сходится в каждой точке, но неравномерно, ибо периодическое продолжение у(х) разрывно. Если же мы положим у0(x)=x то функция у(x)-у0(х), изображенная пунктиром на рис. 2, имеет непрерывное периодическое продолжение, и ее ряд Фурье сходится к ней равномерно. Скорость сходимости ряда при этом также возрастает.
Замечание 3. Алгебраический многочлен наилучшего среднеквадратичного приближения обладает свойством, напоминающим лагранжеву интерполяцию: разность у(x) – Pn(x) на интервале (а, b) имеет не менее n+1 нуля.
Рис. 2.
В самом деле, предположим обратное: нули этой разности суть , где . Составим многочлен
тогда произведение [у (х) - Рп (х)] Qm (x) не меняет знак, следовательно,
Но если в (3) положить , то квадратные скобки в сумме должны обратиться в нуль. Полученное противоречие доказывает наше утверждение.
1.3. Суммирование рядов Фурье.
Нахождение наилучшего приближения приводит к суммированию рядов. Казалось бы, просуммировать ряд нетрудно. Но, во-первых, он далеко не всегда сходится равномерно, даже при наличии сходимости в каждой точке. Так, если у(х) = 1 на первой половине периода и у(х) = 0 на второй, то максимум частной суммы тригонометрического ряда Фурье стремится к 1,09 при (явление Гиббса, рис. 3), хотя в любой точке, кроме точки разрыва, этот ряд сходится к функции.
Во-вторых, если надо суммировать много членов ряда, то происходит большое накопление погрешности входных данных и даже погрешности округления. Например, ряд Тейлора для y(x) = sinx сходится при любых значениях аргумента. Вычислим sin 2550°, используя ЭВМ с 16 значащими цифрами и прекращая вычисления, когда очередной член ряда будет менее 10-8. Получим бессмысленный ответ: sin 2550° = 29,5!
Причина состоит в том, что вычисления с заданным количеством цифр эквивалентны внесению погрешности в коэффициенты ряда. Погрешности вносятся и в том случае, если находить коэффициенты по формулам (4) не аналитически, а численно. А бесконечные ряды, вообще говоря, неустойчивы по отношению к погрешности коэффициентов. В самом деле, изменим все коэффициенты, ак ряда Фурье на малые величины ; тогда сумма ряда изменится на
т. е. при изменение суммы бесконечно велико. Таким образом, суммирование бесконечного ряда Фурье является некорректной задачей, и требуется для этого регуляризация суммирования.
1.4. Метод наименьших квадратов.
Если вещественные функции заданы таблично, т. е. на конечном множестве точек, то их скалярное произведение определяется формулой
где N — полное число узлов таблицы. Тогда условие наилучшего среднеквадратичного приближения примет вид
Выберем линейную аппроксимацию
с числом членов . Тогда коэффициенты аппроксимации находятся из уравнений (3), где скалярные произведения надо брать согласно (5); эти уравнения можно получить и непосредственно, подставляя обобщенный многочлен в (6) и приравнивая нулю производные по коэффициентам. Описанный способ нахождения аппроксимации называется методом наименьших квадратов. Метод наименьших квадратов широко используют для обработки экспериментальных кривых, точки которых измерены с заметной погрешностью . В этом случае весу придают смысл точности измерения данной точки: чем выше точность, тем большее значение веса приписывают точке. Аппроксимирующая кривая будет проходить ближе к точкам с большим весом. Сходные соображения используют в математической постановке задачи: выбирают весовую функцию большой при тех значениях аргумента, где нужно получить более высокую локальную точность аппроксимации.
Если число коэффициентов аппроксимации п взять равным числу узлов N, то среднеквадратичная аппроксимация совпадет с лагранжевой интерполяцией. Очевидно, при наличии значительных ошибок эксперимента интерполяция неразумна. Это хорошо видно из рис. 4, показывающего описание измерений радиоактивного распада в выравнивающих переменных интерполяционным многочленом (пунктир) и прямой, найденной методом
наименьших квадратов. Поскольку при среднеквадратичная аппроксимация близка к интерполяции, то хорошее сглаживание ошибок эксперимента будет при ; но если n слишком мало, то для описания сложной кривой коэффициентов может не хватить. Должно существовать какое-то оптимальное число коэффициентов; оно зависит от функции у(х), числа узлов N, их расположения, весов и от выбранной системы .
Оптимальное число коэффициентов определяют следующим образом. Выбирают некоторое п, находят из условия (6) соответствующие коэффициенты , вычисляют полученное при этом среднеквадратичное уклонение и сравнивают его с известной погрешностью эксперимента. Если , т. е. математическая погрешность аппроксимации много больше физической погрешности исходных данных, то число коэффициентов недостаточно для описания у(х), и надо увеличить п. Если , то старшие коэффициенты аппроксимации физически недостоверны, и надо уменьшить п. Если , то число коэффициентов оптимально.
Обычно начинают расчет с n = 1, когда наверняка , и увеличивают число коэффициентов до тех пор, пока не выполнится условие . Если при этом , то вид аппроксимирующей функции выбран удачно. Если же , то следует поискать более подходящий вид аппроксимирующей функции.
§2. Приближение функций, заданных таблицей,
тригонометрическими многочленами по методу
наименьших квадратов
Пусть узлы расположены на отрезке (0, 2π]:
и в качестве системы Чебышева возьмем тригонометрические функции:
1, cos x, sin x, cos 2x, sin 2x, ..., cos nx, sin nx. (1)
Будем предполагать, что . В этом случае согласно общей теории будет однозначно определяться тригонометрический многочлен
наилучшего приближения в смысле метода наименьших квадратов для произвольной функции, заданной в точках xi. Коэффициенты этого тригонометрического многочлена будут удовлетворять системе уравнений
Решив эту систему, мы сумеем найти приближающий многочлен.
Как мы знаем, система упростится, если функции системы Чебышева ортогональны в смысле той метрики, которая нами вводится при изучении табличных функций. Для тригонометрических многочленов оказывается, что не нужно производить никакой ортогонализации, если и узлы равноотстоящие.
Пусть
Тогда справедливы следующие равенства:
если k+r и k - r не являются кратными N и .
В силу полученных нами равенств система для определения коэффициентов упростится и примет вид
или
Последние формулы носят название формул Бесселя. Заметим, что формулы Бесселя можно получить из формул для коэффициентов Фурье функции f(x):
если вычислять входящие в них интегралы приближенно, используя формулу трапеций, полагая .
Укажем также на связь коэффициентов, полученных по формулам Бесселя, и коэффициентов ряда Фурье функции f(x), если эта функция разлагается в равномерно сходящийся ряд Фурье:
Учитывая наши равенства и беря N=2p, будем иметь:
Таким образом,
Если коэффициенты быстро убывают, то основное значение имеют первые члены этих рядов. При небольших r аr и br будут близки к , а при больших r расхождение будет, вообще говоря, больше.
§3. Реализация и тестирование метода наименьших квадратов.
3.1. Описание программы
3.2. Тестирование программы
Заключение
В данной работе, а конкретно в теоретической части, были рассмотрены некоторые из часто применяемых на практике методов решения функций. Каждый из рассматриваемых методов имеет свои достоинства и недостатки, но все же они позволяют без особых затрат получить искомое решение. Особое внимание было уделено рассмотрению метода наименьших квадратов для решения функций. Именно стремление повысить вычислительную эффективность алгоритма при выполнении его на ЭВМ привело к разработке этого метода. Мной была написана программа, которая находит решение у(х) уравнения , которое при заданном значении х0 аргумента х принимает заданное значение и . В конкретном случае в практической части моей работы находится точное решение уравнения на отрезке [0,1], удовлетворяющее начальным условиям , с шагом h=0,2. Пользователь может получить меньше значений на рассматриваемом отрезке, чем необходимо, или больше. В результате было выявлено, что метод Рунге – Кутты четвертого порядка точности является достаточно точным.
Литература:
1. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М: Наука, 1987.
2. Вержбицкий В.М. Основы численных методов. М.: Высшая школа. 2002.
3. Калиткин Н.Н. Численные методы. М: Наука, 1987.
4. Крылов В.И. и др. Вычислительные методы, т.И. М.: Наука, 1977.
Листинг программы.
Program Rynge2;
uses crt;
type mas=array[1..10] of real;
//----------------------------
var Y,Y1,k1,k2,k3,k4: mas;
a,b,h,x1,x:real;
i,n,nn,m:integer;
//----------------------------
function F(m:integer;x:real;y:mas):
begin
case m of
1: F:=y[2];
2: F:=2*x-y[1]+y[2];
else F:=0;
end;
end;
//----------------------------
begin
clrscr;
writeln('Введите количество уравнений = 2');
read(m);
writeln('Задайте начальные условия y(x)= ');
for i:=1 to 2 do read(Y[i]);
writeln('Введите количество отрезков разбиения nn=');
read(nn);
writeln('Введите отрезок a,b ');
read(a,b);
h:=(b-a)/nn;
//----------------------------
for n:=0 to nn-1 do
begin
x:=a+h*n;
writeln('x=',x);
for i:=1 to m do k1[i]:=F(i,x,Y);
for i:=1 to m do Y1[i]:=Y[i]+h*k1[i]/2;
x1:=x+h/2;
for i:=1 to m do k2[i]:=F(i,x1,Y1);
for i:=1 to m do Y1[i]:=Y[i]+h*k2[i]/2;
for i:=1 to m do k3[i]:=F(i,x1,Y1);
for i:=1 to m do Y1[i]:=Y[i]+h*k3[i];
x1:=x+h;
for i:=1 to m do k4[i]:=F(i,x1,Y1);
for i:=1 to m do
begin
Y[i]:=Y[i]+h*(k1[i]+2*k2[i]+2*
end;
//----------------------------
writeln('OTBET: Y(1)=',Y[1]:3:7);
writeln('OTBET: Y(2)=',Y[2]:3:7);
end;
end.