Численные методы
Особенности решения алгебраических, нелинейных, трансцендентных уравнений. Метод половинного деления (дихотомия). Метод касательных (Ньютона), метод секущих. Численные методы вычисления определённых интегралов. Решение различными методами прямоугольников.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 15.02.2010 |
| Размер файла | 473,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Содержание
- Решение алгебраических, нелинейных и трансцендентных уравнений
- Метод половинного деления (дихотомия)
- Метод простых итераций
- Метод касательных (Ньютона)
- Метод секущих
- Численные методы вычисления определённых интегралов
- Метод левых прямоугольников
- Метод правых прямоугольников
- Метод средних прямоугольников
- Метод трапеций
- Метод Симпсона
- Приближение функций
- Интерполяция
- Аппроксимация
- Список использованной литературы
Решение алгебраических, нелинейных и трансцендентных уравнений
Пусть задана непрерывная функция f(х) и требуется найти все или некоторые корни уравнения
f(x)=0. (1)
Эта задача распадается на несколько задач. Во-первых, надо исследовать количество, характер и расположение корней. Во-вторых, найти приближенные значения корней. В-третьих, выбрать из них интересующие нас корни и вычислить их с требуемой точностью.
Первая и вторая задачи решаются аналитическими и графическими методами.
Когда ищутся только действительные корни уравнения, то полезно составить таблицу значений f(x). Если в двух соседних узлах таблицы функция имеет разные знаки, то между этими узлами лежит нечетное число корней уравнения (по меньшей мере, один). Если эти узлы близки, то, скорее всего, корень между ними только один. Но выявить по таблице корни чётной кратности** Кратными корнями называются совпадающие по значению корни. Например, известно, что уравнение y=x2 имеет корень x=0, но правильнее утверждать, что это уравнение имеет 2 кратных корня x1=0 и x2=0. сложно. По таблице можно построить график функции у=f(х) и графически найти точки его пересечения с осью абсцисс. Этот способ более нагляден и дает неплохие приближенные значения корней. Во многих задачах техники такая точность уже достаточна. В технике еще популярны графические методы решения уравнений (номография). Построение графика позволяет выявить даже корни чётной кратности.
Иногда удается заменить уравнение (1) эквивалентным ему уравнением (х)=(х), в котором функции y1=(х) и y2=(х) имеют несложные графики. Например, уравнение хsinх--1=0 удобно преобразовать к виду sinx=l/x. Абсциссы точек пересечения этих графиков будут корнями исходного уравнения.
Приближенные значения корней уточняют различными итерационными методами. Рассмотрим наиболее эффективные из них.
Метод половинного деления (дихотомия)
Пусть мы нашли такие точки a и b что f(a)f(b)0, т. е. на отрезке [a,b] лежит не менее одного корня уравнения. Найдем середину отрезка xc=(a+b)/2 и вычислим f(xc). Из двух половин отрезка выберем ту, для которой f(xc)f(a или b)0, т.е. отрезок на котором функция меняет знак. Затем новый отрезок опять делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис. 1).
Если требуется найти корень с точностью , то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше 2. Тогда середина последнего отрезка даст значение корня с требуемой точностью. Дихотомия проста и очень надежна: к простому корню она сходится для любых непрерывных функций f(x), в том числе недифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости невелика: за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трех цифр требует 10 итераций (т.к. длина отрезка, на котором лежит корень, после 10 итераций равна 1/210=1/102410-3). Зато точность ответа гарантируется.
Перечислим недостатки метода.
1. Для начала расчета надо найти отрезок, на котором функция меняет знак.
2. Если в этом отрезке несколько корней, то заранее неизвестно, к какому из них сойдется процесс (хотя к одному из них сойдется).
3. Метод неприменим к корням четной кратности.
4. Для корней высокой нечетной кратности он сходится, но менее точен и хуже устойчив к ошибкам округления, возникающим при вычислении f(x).
5. Наконец, на системы уравнений дихотомия не обобщается.
Утверждение 1. С помощью данного метода невозможно найти корни чётной кратности.
Доказательство.
Чётно кратный корень это корень уравнения вида
(x+a)2n=0, где n - целое, n[0,]. (2)
Решением этого уравнения будет корень x=-a кратности 2n. В общем виде уравнение может иметь как чётно, так и нечётно кратные корни. Можно записать общий вид уравнения имеющего (k+m) только действительных корней так:
(x+x1)2n1(x+x2)2n2…(x+xk)2nk(x+xk+1)2n(k+1)+1(x+xk+2)2n(k+2)+1…(x+xk+m)2n(k+m)+1=0, (3)
где n1,…,n(k+m) [0,] - целые числа; x1 x2… xk+m.
В уравнении (3) k чётно кратных и m нечётно кратных корней. Оно раскладывается на (k+m) уравнений, из которых легко получаются корни. Если задать начальный отрезок [-x1-r,-x1+r], где r - мало, и проверить условие смены знака функции на его границах, то обнаружим, что знак не меняется в силу чётности степени. А если аналогично проверить нечётно кратные корни, то получим обратную ситуацию.
Следствие 1.
Если корень имеет чётную кратность, то на границах бесконечно малого отрезка с центром в этом корне функция имеет одинаковые знаки.
Следствие 2.
Если корень имеет нечётную кратность, то на границах бесконечно малого отрезка с центром в этом корне функция имеет разные знаки.
Пусть на заданном отрезке [a,b] лежит 1 корень чётной кратности, тогда в силу следствия 1 на границах отрезка знак меняться не будет, что означает остановку выполнения итераций и недостижение необходимой точности. Если же на отрезке [a,b] лежит 1 чётно кратный корень и 1 нечётно кратный корень, то чётно кратный корень будет просто игнорирован методом, т.к. условие смены знака являющееся также основным условием, с помощью которого определяется корень на текущем полуотрезке, в силу следствия 1 не выполнится. Следовательно, чётно кратный корень не может быть найден с помощью данного метода.
Утверждение 2. Если на концах начального отрезка значения функции имеют один знак, то метод может не сойтись, то есть, возможно, ни один из корней не будет найден с заданной точностью.
Доказательство.
Первым вариантом постоянства знака функции на границах отрезка является отсутствие корня на нём, поэтому исключим этот случай как тривиальный, будем считать, что на отрезке хотя бы один корень существует. Вторым вариантом - существование чётного количества корней.
Если f(a)f(b)0, то продолжать итерации невозможно, т.к. условие смены знака не подтверждается. Если же, тем не менее, на первом шаге не проверять условие смены знака и разделить отрезок пополам, то может возникнуть ситуация, в которой корни распределяться по чётному количеству в каждой половине отрезка. А чётное количество корней означает чётное количество пересечений оси Ox, даже если существуют кратные корни.
Следовательно, условие смены знака вновь не подтвердится для обеих половинок исходного отрезка. Следовательно, дальнейшие итерации не будут выполнены, и не будет достигнута заданная точность.
Утверждение 3. Если на концах начального отрезка значения функции имеют разные знаки, то будет найден с заданной точностью один из корней лежащих на нём.
Доказательство.
В силу утверждения 1 будем рассматривать только корни нечётной кратности. Так как функция меняет знак на концах отрезка, предположим, f(a)?0, f(b)?0. Тогда если f(xc)?0, то для дальнейшего приближения выберем отрезок [xc,b], т.к. f(b)f(xc)?0. Если же f(xc)?0, то для дальнейшего приближения выберем отрезок [a,xc], т.к. f(a)f(xc)?0.Для второго случая, когда f(a)?0, f(b)?0 аналогично доказывается существование одного из полуотрезков, на котором функция меняет знак. Из чего следует, что после каждой итерации для одного из полуотрезков условие смены знака обязательно будет выполнено. Следовательно, нет причин для остановки итерационного процесса, который завершится лишь по достижении заданной точности.
Построим блок-схему алгоритма вычисления корня уравнения вида (1) с помощью метода дихотомии. Пусть на начальном отрезке [a,b] функция меняет знак, т.е. на этом отрезке существует нечётное количество нечётно кратных корней. Пример такой функции изображён на рис. 1. Необходимо найти корень xт с точностью е. Будем считать xт точным значением корня, xч - значение корня полученное данным методом, тогда задача считается выполненной, если xч[xт-е,xт+е].
Дихотомия применяется тогда, когда требуется высокая надежность счета, а скорость сходимости малосущественна.
Метод простых итераций
Основной принцип метода заключается в том, что уравнение (1) представляется в виде:
x=ц(x), (4)
где ц(x) можно определить многими способами, например, так:
ц(x)=x-бf(x), б=const, или
ц(x)=x+ш(x)f(x),
где ш(x) - произвольная, непрерывная, знакопостоянная функция на отрезке [a,b].
Метод простых итераций в силу (4) определяется следующей рекурсивной формулой:
xn+1=ц(xn), где n=0,1,2,… (5)
Здесь n имеет смысл номера итерации, x0 - некоторое начальное приближение. Из (5) видно, что если xn>xт, то этот предел и есть корень уравнения (рис. 2).
Пусть в окрестности точки xт (xт-Д,xт+Д), где Д>0 функция ц(x) удовлетворяет условию Липшица:
|ц(x2)-ц(x1)|?q|x2-x1| (6)
для любых x2,x1(xт-Д,xт+Д),
0<q<1, (7)
при этом x0(xт-Д,xт+Д), (8)
причём, (xт-Д,xт+Д) [a,b].
В связи с этим допущением можно сделать несколько утверждений.
Утверждение 1.
Полученные с помощью (5) xn(xт-Д,xт+Д) для любого целого n?0.
Доказательство
В силу (8)
|x0-xт|<Д,
из (5),(6) и (7) получим
|x1-xт|=|ц(x0)-ц(xт)|?q|x0-xт|,
|x2-xт|=|ц(x1)-ц(xт)|?q|x1-xт|?q2| x0-xт|,
|xn-xт|=|ц(xn-1)-ц(xт)|?q|xn-1-xт|?q2| xn-2-xт|?…? qn| x0-xт|<Д, (9)
Из последнего неравенства |xn-xт|<Д следует, что для любого целого n?0 верно утверждение 1.
Утверждение 2.
Последовательность {xn} сходится при n>? к пределу xт, являющемуся корнем уравнения.
Доказательство.
В силу (5) и (6):
|xn+m-xn|=|ц(xn+m-1)-ц(xn-1)|?q|xn+m-1-xn-1|?q2|xn+m-2-xn-2|?…?qn|xm-x0| (10)
Следовательно, в силу (7) для любого целого
m?0
Значит в силу признака Коши** Признак Коши. Для того чтобы последовательность {xn} имела предел, необходимо и достаточно, чтобы для любого как угодно малого положительного числа е существовал такой номер N=Nе, при котором для любых n?N и всех целых положительных m выполнялось неравенство |xn+m-xn|<е, другими словами предел существует . Докажем теперь, что xlim=xт. Из (10) следует (для определённости возьмём m=1), что , т.е. при n>? xlim=xn+1=xn, а в силу (5) xn+1=ц(xn) => xlim=xn=ц(xn) => xlim=ц(xlim). Из этого равенства следует, что xlim есть корень уравнения (4), т.е. xlim=xт.
Утверждение 3.
На интервале (xт-Д,xт+Д) существует только 1 корень уравнения (2).
Доказательство.
Пусть существует 2 корня
x1 и x2?x1, тогда в силу (4) x1=ц(x1), x2=ц(x2).
Из (6) следует |x2-x1|=|ц(x2)-ц(x1)|?q|x2-x1|, т.е. |x2-x1|?q|x2-x1|.
Из этого следует, что q=1, а это противоречит (7). Следовательно, корень только 1.
Следует так же отметить, что если ц(x) имеет на интервале (xт-Д,xт+Д) непрерывную производную, то (6) выполняется, когда
|ц?(x)|?q => |ц?(x)|<1 для x(xт-Д,xт+Д). (11)
Если |ц?(xт)|<1, x0(xт-Д,xт+Д), то итерации сойдутся.
Если |ц?(xт)|>1, то в силу непрерывности производной |ц?(x)|>1 и на некотором интервале (xт-Д1,xт+Д1), поэтому итерации не сойдутся к корню. Если же |ц?(xт)|<1, но x0(xт-Д,xт+Д), т.е. |ц?(x0)|>1, то в данном случае о сходимости процесса можно судить только после дополнительного анализа функции ц(x).
Как и при поиске решения методом дихотомии будем считать задачу выполненной, если найденное некоторое значение xч[xт-е,xт+е], где е - заданная точность. Для определения того, когда можно прекратить итерации, т.е. когда достигнута заданная точность, подробнее рассмотрим неравенство (9). По сути, нам необходимо добиться выполнения следующего неравенства:
|xn+1-xт| ? е, (12)
а в силу того, что из (9) можно получить неравенство
|xn+1-xт| ? qn+1|x0-xт|,
где q можно определить как для любого целого n?1, выведем условие достижения заданной точности (12). Введём обозначения
дn+1=|xn+1-xт|. Из (9) ,
а так же очевидно, что д0-дn+1=|x0-xn+1|=о, тогда:
д0=дn+1+о
дn+1=gд=g(дn+1+о)
. (13)
Неравенство (13) является условием остановки процесса итераций, т.е. условием достижения заданной точности. В завершение рассмотрения данного метода остаётся только построить блок-схему его алгоритма. Будем считать, что |ц?(xт)|<1, x0(xт-Д,xт+Д).
Метод касательных (Ньютона)
Метод Ньютона называют также методом касательных и методом линеаризации. Суть метода заключается в том, что в точке приближения к функции строится касательная (Рис. 3). Следующая точка приближения - это точка пересечения полученной прямой с осью Ox. Процесс продолжается вплоть до достижения заданной точности.
Из рисунка очень легко получить итерационную формулу метода, используя геометрический смысл производной. Если f(x) имеет непрерывную производную f'(x)?0, тогда получим
Аналогично получаем x2, x3, и т.д. Таким образом, можем записать общую формулу:
Метод Ньютона можно рассматривать, как частный случай метода простых итераций, если задать
.
В этом случае
Условие сходимости метода простых итераций можно переписать для метода Ньютона следующим образом:
(14)
Рассуждения по поводу выбора начального приближения в методе Ньютона такие же, как и в методе простых итераций, только вместо (11) используется (14). Для данного метода также применимо (13). Напишем блок-схему алгоритма метода Ньютона.
Метод секущих
В данном методе, в отличие от метода Ньютона, проводятся не касательные, а секущие (Рис. 4). Из рисунка легко получить итерационную формулу:
. (15)
В качестве начального приближения необходимо задать не только x0, но и x1. Метод секущих имеет одно преимущество перед методом Ньютона - здесь не нужно вычислять производную. Но этот метод имеет также существенные недостатки. Сходимость итераций может быть немонотонной не только вдали от корня, но и в малой окрестности корня.
В знаменателе формулы (15) стоит разность значений функции. Вдали от корня это не существенно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счёта. Это ограничивает точность, с которой можно найти корень; для простых корней это ограничение не велико, а для кратных может быть существенным.
От «разболтки» страхуются так называемым приёмом Гаврика. Выбирают не очень малое е, ведут итерации до выполнения условия |xn+1-xn|<е и затем продолжают расчёты до тех пор, пока |xn+1-xn| убывают. Первое же возрастание обычно означает начало «разболтки»; тогда расчёт прекращают и последнюю итерацию не используют. Все ограничения по сходимости итераций для данного метода такие же, как и в методах простых итераций и Ньютона. А вот определение достижения заданной точности, как видно из описания метода, затруднительно, и, даже, возможна ситуация, когда из-за «разболтки» счёта заданная точность не будет достигнута никогда. При использовании метода секущих в явном виде определить точность трудно, поэтому используют косвенный метод. Считают, что вблизи корня |xn+1-xn||xт-xn+1|. Конечно эта оценка весьма примерна, но при больших n (в идеале при n>?) это так и есть. Построим блок-схему алгоритма данного метода с использованием приёма Гаврика.
Численные методы вычисления определённых интегралов
Метод левых прямоугольников
Эти методы численного интегрирования основываются на геометрическом смысле интеграла. Как известно интеграл есть площадь криволинейной трапеции ограниченной подынтегральной функцией f(x) на отрезке [a,b]. Для вычисления интеграла I отрезок [a,b] разбивают на n отрезков длиной h. На каждом отрезке криволинейную трапецию приближают прямоугольником, так как его площадь можно легко вычислить. Затем суммируют все полученные площади, получая тем самым приближённое значение интеграла. На рис. 5 проиллюстрирован, так называемый, метод левых прямоугольников. Его название объясняется тем, что высота прямоугольника f(x) вычисляется в левой границе отрезка h. Выведем формулу для приближённого вычисления интеграла I.
Как видно из рисунка площадь первого слева прямоугольника S0=f(x0)h. Площадь следующего S1=f(x1)h. Легко заметить, что площадь i-го прямоугольника Si=f(xi)h. Всего таких прямоугольников n, нумерация их ведётся от 0 до n-1. Таким образом, приближённое значение интеграла, полученное этим методом, вычисляется по формуле:
. (16)
Оценим погрешность формулы (16) на отрезке [xi,xi+h]. Для этого разложим функцию f(x) по формуле Тейлора, выбирая xi за центр разложения и предполагая наличие у функции требуемых по ходу рассуждений непрерывных производных.
f(x)=f(xi)+(x-xi)f'(xi)+… (17)
В формуле (17) для определённости отбросим члены, содержащие производные высших порядков, т.е. 2-ю и выше. Тогда получим:
, т.е.
(18)
Чтобы получить общую погрешность метода на отрезке [a,b] просуммируем все RЛi:
(19)
Поскольку в (17) были отброшены члены, содержащие более высокие степени длины интервала, то выражение остаточного члена (19) является асимптотическим, т.е. выполняющимся при h>0 с точностью до членов более высокого порядка малости. Но для справедливости этой оценки необходимо существование непрерывной f'(x); если f'(x) кусочно-непрерывна, то удаётся сделать лишь мажорантную оценку
(20)
Эту формулу можно записать иначе
, (21)
где n - количество отрезков, на которые разбит отрезок [a,b].
Перед началом вычислений по данному методу необходимо определиться с h или, что, по сути, то же самое, с n. Пусть известны границы отрезка [a,b], задана подынтегральная функция f(x) и точность е, с которой должен быть вычислен интеграл. Чтобы определить h и n воспользуемся простым и очевидным неравенством:
|RЛ|?е, (22)
откуда получаем для непрерывной f'(x):
(23)
либо если учесть, что получим
. (24)
Для кусочно-непрерывной f'(x) с учётом (20) и (21) справедливо следующее
(25)
(26)
Метод правых прямоугольников
Этот метод похож на предыдущиу. Отличие в том, что высота прямоугольников вычисляется по правой границе (Рис. 6).
Выводы формул для данного метода аналогичны предыдущему. Основные отличия заключаются в нумерации. Формула метода правых прямоугольников выглядит следующим образом:
. (27)
Рассуждения и конечные формулы, связанные с определением погрешности метода и выбором ширины основания прямоугольников аналогичны тому, что получено в предыдущем методе.
Метод средних прямоугольников
Чтобы уменьшить погрешность методов левых и правых прямоугольников был предложен метод средних, т.е. метод в котором высота прямоугольника вычисляется в середине отрезка h (Рис. 7). Обращаясь к рисунку легко увидеть, что площади прямоугольников вычисляются по следующим формулам:
(28)
Оценим погрешность формулы (28) на отрезке [xi,xi+h]. Прежде всего, получим разложение по формуле Тейлора для данного метода. Центр разложения в данном случае будет точка . Тогда получим:
(29)
В формуле (29) отбросим члены, содержащие 3-ю и выше производные. Получаем:
Ii-IСр.i=RСр.i
, т.е.
. (30)
Аналогично тому, как были получены формулы (20), (21), (23), (24), (25) можно получить формулы, по которым оцениваются n и h, для данного метода. Запишем окончательные формулы для непрерывной f''(x).
(31)
(32)
Для кусочно-непрерывной f''(x) получаем мажорантные оценки:
(33)
(34)
Сравнивая формулы (19) и (30) погрешностей методов приходим к выводу, что погрешность метода средних во много раз ниже погрешности метода левых или правых прямоугольников, т.е. метод средних во много раз точнее и для достижения заданной точности требует меньше машинного времени. Поэтому блок-схему построим именно для метода средних.
Введём обозначение. [n] - целая часть n, полученная путём отбрасывания дробно части. Для вычисления интеграла дано е, [a,b], f(x), f''(x). Прежде всего, через е необходимо получить n. Пользоваться формулой (32) мы не будем, т.к. в ней необходимо вычислять интеграл. Воспользуемся мажорантной оценкой (34). Для этого перед вычислением интеграла необходимо найти , но это легко осуществимо с помощью небольшого циклического процесса. Для него понадобиться знание количества разбиений , на которых будем вычислять значения второй производной. Обозначим это количество n1.
Метод трапеций
Метод трапеций основан на том, что криволинейная трапеция приближается прямолинейной (Рис. 8). Т.е. площади вычисляются по следующей формуле:
Таким образом, получаем общую формулу трапеций:
. (35)
Теперь оценим погрешность метода. Вывод формулы погрешности аналогичен выводу (30), поэтому приведём сразу окончательную оценку погрешности для непрерывной f''(x):
; (36)
для кусочно-непрерывной f''(x):
(37)
Оценивая n и h, получим:
(38)
(39)
Для кусочно-непрерывной f''(x):
(40)
(41)
Как видно из полученных формул погрешность метода средних примерно вдвое меньше погрешности метода трапеций. Очевидно, что если функция определена на всём интервале, лучше пользоваться методом средних, метод трапеций используют обычно для функций определённых только в узлах сетки. Знаки главного члена погрешности у формул трапеций и средних разные. Поэтому, если есть расчёты по обеим формулам, то точное значение интервала лежит, как правило, в вилке между ними. Деление этой вилки как 2:1 даёт уточнённый результат близкий к тому, который получается при использовании более точного метода Симпсона.
Метод Симпсона
Этот метод основан на том, что функция f(x) приближается на отрезке [xi-h, xi+h] параболой (причём xi отстоит от xi+1 на расстоянии 2h) (Рис.9). То есть через заданные точки проводится парабола. Но известно, что уравнение параболы имеет вид с(x)=ax2+bx+c, т.е. чтобы определить коэффициенты a, b, c необходимо решить систему из трёх уравнений, а для этого необходимо знать координаты как минимум трёх точек, через которые проходит парабола с(x). В связи с этим, в отличие от предыдущих методов, для вычисления площади отдельной криволинейной трапеции понадобиться не две, а три точки. Для вывода формулы Симпсона рассмотрим подробнее i-ю криволинейную трапецию ограниченную сверху параболой сi(x).
Для упрощения расчётов сделаем следующие преобразования. Перенесём i-ю криволинейную трапецию в начало координат так, что xi=0 (следовательно, xi-h=-h, xi+h=h). Очевидно, что её площадь не изменится. Найдём её площадь (Рис. 10). Для нахождения площади криволинейной трапеции необходимо знать форму кривой ограничивающей её. В нашем случае это парабола . Для нахождения коэффициентов ai, bi, ci составим систему из трёх уравнений. Для простоты обозначим
ai?a, bi?b, ci?c, f(xi-h)?f0, f(xi)?f1, f(xi+h)?f1.
Тогда
Таким образом, получаем
. (42)
. (43)
Таким образом, получаем общую формулу Симпсона:
Для упрощения этой формулы учтём, что
, , ,
где a и b - границы отрезка интегрирования [a, b]. С учётом этого получим:
,
где n - количество отрезков длиною 2h. То есть количество отрезков h, на которые разбит отрезок [a, b] должно быть обязательно чётным. Длина отрезка [a, b] равна 2nh.
Для оценки погрешности формулы Симпсона на отрезке [xi-h, xi+h] разложим функцию f(x) по формуле Тейлора до пятого члена с центром разложения в точке xi. То есть
(44)
Тогда с учётом (43) и (44) получим:
Т.е.
, (45)
Сравнив формулы (45), (36), (30) и (19) увидим, что метод Симпсона является наиболее точным из всех описанных методов численного интегрирования.
Учитывая, что для метода Симпсона , запишем формулы оценки n и h для заданного е. Для непрерывной :
,
.
Мажорантные оценки для кусочно-непрерывной :
,
.
Построим блок-схему.
Приближение функций
Как известно, функцию можно задать многими способами. Самые распространённые из них - это аналитический, графический и табличный. В первых двух способах функция обычно определена на бесконечном числе точек, третий же способ задаёт лишь их конечное количество, например, экспериментальные данные или результаты сложных вычислений. В связи с этим встаёт вопрос получения промежуточных значений таблично заданной функции. Для их нахождения используют два способа: интерполяция (экстраполяция)** Экстраполяция отличается от интерполяции тем, что этим методом пытаются вычислить следующее за последним значение или стоящее до первого заданного, а не промежуточное как при интерполяции. и аппроксимация. При использовании интерполяции считают табличные значения точными и интерполяционный многочлен должен точно проходить через заданные точки (Рис. 11). Аппроксимирующая же функция лишь приближается как можно ближе к заданным точкам, но не обязательно через них проходит (Рис. 13). Это связано с тем, что табличные данные считаются приближенными, и точное прохождение функции через эти точки будет только увеличивать ошибку.
Интерполяция
Итак, как было сказано выше, задачей интерполяции является поиск такого многочлена, график которого проходит через заданные точки.
Пусть функция y=f(x) задана с помощью таблицы (табл. 1).
Таблица 1
|
x |
x0 |
x1 |
x2 |
… |
xn |
|
|
y |
y0 |
y1 |
y2 |
… |
yn |
Необходимо получить многочлен Pn(x) такой, чтобы выполнялось условие:
Pn(xi)=yi. (46)
Для этого зададимся конкретным видом многочлена. Пусть Pn(x) имеет следующий вид:
Pn(xi)=a0+a1x+a2x2+…+anxn. (47)
Для того, чтобы определить коэффициенты a0, a1,… необходимо решить систему из n уравнений с n неизвестными:
(48)
Полином с коэффициентами, полученными путём решения системы (48) называют интерполяционным полиномом Лагранжа и обозначают Ln(x). Решение системы (48) весьма трудоёмко, поэтому интерполяционный полином Лагранжа представляют в виде линейной комбинации многочленов степени n:
. (49)
Необходимо, чтобы каждый многочлен li(x) обращался в нуль во всех узлах интерполяции, за исключением i-го, в котором он равен 1 (Рис. 12). Если li(x) удовлетворяет таким условиям, то в i-ом узле интерполяции многочлен Ln(x) примет значение yi, что удовлетворяет условию поставленной задачи. Таким условиям удовлетворяет многочлен вида:
. (50)
Таким образом, интерполяционный многочлен Лагранжа можно представить следующей общей формулой:
(51)
С использованием формулы (51) построим блок-схему алгоритма метода интерполяции функции полиномом Лагранжа.
Аппроксимация
В задачу аппроксимации входит нахождение такой функции y=f(x), что расстояния между заданными точками yi и значениями f(xi) были минимальными (Рис. 13). Обозначим отклонение:
еi=yi-f(xi)
В качестве оценки общего отклонения кривой f(x) от табличных данных (Табл. 1) можно было бы взять сумму отклонений еi, но отклонения могут быть разными по знаку и, не смотря на большие еi их сумма может быть близка к нулю. Очевидно, что необходимо брать сумму абсолютных значений отклонений, но на практике неудобно пользоваться этой функцией, поэтому в качестве критерия оценки отклонения кривой берут сумму квадратов отклонений:
. (52)
Для определения функции f(x) необходимо, во-первых, задать её общий вид, например, f(x)=ax+b, во-вторых, подставив f(x) в (52) и минимизировав у, найти коэффициенты (a и b). Такой метод определения коэффициентов для функции f(x) называется методом наименьших квадратов. Наиболее часто встречающиеся виды функции f(x) для метода наименьших квадратов приведены в таблице 2. Формула y=f(x) называется эмпирической формулой или уравнением регрессии y на x.
Таблица 2
|
Общий вид функции |
Аналитическая формула |
Вид регрессии |
|
|
y=f(x,a,b) |
y=ax+b |
линейная |
|
|
y=f(x,a,m) |
y=axm |
степенная |
|
|
y=f(x,a,m) |
y=aemx |
показательная |
|
|
y=f(x,a,b) |
дробно-линейная |
||
|
y=f(x,a,b) |
логарифмическая |
||
|
y=f(x,a,b) |
гиперболическая |
||
|
y=f(x,a,b) |
дробно-рациональная |
Рассмотрим подробнее метод наименьших квадратов на примере линейной регрессии, т.е. общий вид функции такой: f(x)=ax+b. Требуется найти методом наименьших квадратов коэффициенты a и b. Для определения минимального у необходимо приравнять нулю частные производные этой функции по параметрам a и b. Для случая линейной регрессии формула (52) приводится к следующему виду:
. (53)
Условие экстремума запишется так:
. (54)
Отсюда получаем систему из двух уравнений с двумя неизвестными.
(55)
(56)
(57)
Итак, коэффициенты линейной регрессии вычисляются по формулам (57), но для определения параметров других видов регрессии выводить аналогичные формулы необязательно. Можно воспользоваться уже полученными. Для этого будем приводить все виды регрессии к линейному виду.
Степенная регрессия
Прологарифмируем степенную зависимость при условии, что x>0 и a>0.
В общем виде линейную зависимость будем записывать так:
Y=AX+B. (58)
Для линейной регрессии Y=y A=a, X=x, B=b. Для регрессии степенной:
.
То есть для того, чтобы воспользоваться формулами (57) необходимо вместо подставлять , вместо - . Тогда по первой формуле определяющей значение параметра A получим значение m, а по второй - значение . Следовательно, остаётся небольшое преобразование для получения a: .
Перепишем формулы (57) в общем виде с учётом (58).
. (59)
Показательная регрессия
Сделаем следующее преобразование:
.
Тогда (a>0, y>0).
Дробно-линейная регрессия.
(y?0).
Логарифмическая регрессия
(x>0).
Гиперболическая регрессия
(x?0).
Дробно-рациональная регрессия
(x?0, y?0).
Построим блок-схему алгоритма вычисления коэффициентов a и b для линейной регрессии.
Список использованной литературы
1. Калиткин Н.Н. Численные методы. - М.: Наука, 1978. - 512с.
2. Самарский А.А. Введение в численные методы. - М.: Наука, 1982. - 272с.
3. Хемминг Р.В. Численные методы/ Пер. с англ. М.: Наука, 1968. - 400с.
4. Численные методы анализа Б. П. Демидович, И. А. Марон и Э. З. Шувалова. - М.: Наука, 1967. - 368с.
5. Баранов А.В., Рябчук Э.В. Численные методы в инженерных задачах. - Волгоград.: Политехник, 1988. - 128с.
6. Фильчаков П.В. Справочник по высшей математике. - Киев: Наукова думка, 1975. - 500с.
Подобные документы
Общая постановка задачи. Отделение корня. Уточнение корня. Метод половинного деления (бисекции). Метод хорд (секущих). Метод касательных (Ньютона). Комбинированный метод хорд и касательных. Задания для расчётных работ.
творческая работа [157,4 K], добавлен 18.07.2007Биография Исаака Ньютона, его основные исследования и достижения. Описание порядка нахождения корня уравнения в рукописи "Об анализе уравнениями бесконечных рядов". Методы касательных, линейной аппроксимации и половинного деления, условие сходимости.
реферат [1,6 M], добавлен 29.05.2009Трансцендентное уравнение: понятие и характеристика. Метод половинного деления (дихотомии), его сущность. Применение метода простой итерации для решения уравнения. Геометрический смысл метода Ньютона. Уравнение хорды и касательной, проходящей через точку.
курсовая работа [515,8 K], добавлен 28.06.2013Численные методы представляют собой набор алгоритмов, позволяющих получать приближенное (численное) решение математических задач. Два вида погрешностей, возникающих при решении задач. Нахождение нулей функции. Метод половинного деления. Метод хорд.
курс лекций [81,2 K], добавлен 06.03.2009Изучение способов решения нелинейных уравнений: метод деления отрезка пополам, комбинированный метод хорд и касательных. Примеры решения систем линейных алгебраических уравнений. Особенности математической обработки результатов опыта, полином Лагранжа.
курсовая работа [181,1 K], добавлен 13.04.2010Вычисление относительной и абсолютной погрешности табличных определённых интегралов. Приближенные методы вычисления определённых интегралов: метод прямоугольников, трапеций, парабол (метод Симпсона). Оценка точности вычисления "не берущихся" интегралов.
курсовая работа [187,8 K], добавлен 18.05.2019Постановка задачи вычисления значения определённых интегралов от заданных функций. Классификация методов численного интегрирования и изучение некоторых из них: методы Ньютона-Котеса (формула трапеций, формула Симпсона), квадратурные формулы Гаусса.
реферат [99,0 K], добавлен 05.09.2010Геометрическая интерпретация методов Ньютона, итерации и спуска. Определение корня уравнения с заданной степенью точности. Решение систем нелинейных алгебраических уравнений. Нахождение эквивалентного преобразования для выполнения условия сходимости.
курсовая работа [371,6 K], добавлен 14.01.2015Модифицированный метод Ньютона. Общие замечания о сходимости процесса. Метод простой итерации. Приближенное решение систем нелинейных уравнений различными методами. Быстрота сходимости процесса. Существование корней системы и сходимость процесса Ньютона.
дипломная работа [1,8 M], добавлен 14.09.2015Графическое решение нелинейного уравнения. Уточнение значение одного из действительных решений уравнения методами половинного деления, Ньютона–Рафсона, секущих, простой итерации, хорд и касательных, конечно-разностным и комбинированным методом Ньютона.
лабораторная работа [32,7 K], добавлен 11.06.2011
