|
|
Методич_стат-исправлено. Методические указания по курсу Информатика
ЛАБОРАТОРНАЯ РАБОТА № 3
«Уточнение корня уравнения» 1. Цель работы
Получить навыки модульного программирования на примере задачи численного решения нелинейных уравнений. Использование оболочки QBasic для построения программ и головного модуля.
Многие задачи исследования различных объектов с помощью математических моделей, применяемых их для прогноза или расчёта, приводят к необходимости решения нелинейных уравнений.
Уравнения могут быть алгебраическими и трансцендентными. Пример
алгебраического уравнения: y = a + bx + cx², трансцендентного: y = eⁿ + x.
Решить уравнение – это найти такое значение переменной х, при котором заданная функция равна нулю (f (x) = 0).
Как правило, процесс решения нелинейного уравнения общего вида f(х)=0 осуществляется в два этапа. На первом этапе отделяют корни, т.е. находят такие отрезки, внутри которых находится строго один корень. На втором этапе уточняют корень, т.е. находят его значение х* с предварительно заданной точностью ε. В практических задачах решением называют любое значение х, отличающееся по модулю от точного значения х* не более чем на величину ε.
Рассмотрим следующие методы уточнения корня уравнения:
- метод дихотомии;
- метод касательных;
- метод простой итерации;
- метод хорд.
1). Метод дихотомии
Пусть функция f (x) отрицательна в точке a (f (a) < 0), положительна в точке b (f (b) > 0), и непрерывна на отрезке [a, b] график функции пересекает ось Х, т. е. на этом отрезке имеется корень уравнения – точка, в которой
f(х)= 0.
Тот же вывод следует, если f(а) > 0, f(b) < 0. В общем виде это формулируется так: в точках а и b функция f(х) принимает значения разных знаков. Если нам известен хотя бы один такой отрезок, пусть и большой длины, мы можем построить процедуру быстрого и сколь угодно точного поиска корня уравнения. Найдем значение функции в точке с, находящейся в середине отрезка: с =(a + b)/2. Знак f(с) совпадает со знаком функции на одном из концов отрезка и противоположен знаку функции на другом конце.
Пусть разные знаки f(х) в точках а и с. Значит на [а, с] наверняка есть искомый корень уравнения.
Таким образом, мы получили задачу, эквивалентную исходной, но теперь длина отрезка, на котором, как нам известно, находится корень, в два раза короче. Отрезок [а, с] опять можно разделить пополам и оставить в рассмотрении только один из двух получившихся (учитывая знаки значений f(х) на концах этих отрезков). Выбранный отрезок вновь разделить, и продолжать так до тех пор, пока отрезок, на котором находится корень, не станет достаточно мал.
Как написать программу на QuickВаsic, соответствующую этому методу?
Прежде всего, функцию, корень которой мы ищем, лучше всего описать в виде отдельной function. Во время выполнения программа должна запросить начальные значения а и b.
Далее нужно проверить, что f(а) и f(b) действительно разных знаков.
Это условие можно записать двумя разными способами:
((f (а) <= 0) and (f (b) > 0)) or ((f (b) <= 0) and (f (a) > 0))
f (a) * f(b) <= 0
Если это не так, нужно только напечатать сообщение об ошибке, иначе можно приступать к поиску корня. Поиск проще всего оформить в виде цикла:
Do until (b-а) < eps ... loop
Здесь eps - константа, равная, например 10ˉ5. На каждой итерации цикла нужно вычислить значение точки с и сравнить знак функции в этой точке со знаком f(а). Если знаки разные, о точке b можно "забыть": b:=с. Иначе – "забываем" о точке а. После окончания цикла остается лишь напечатать найденный корень. Ближе всего к корню будет, середина окончательного отрезка [а,d], длина которого не превышает заданной точности eps.
2). Метод касательных
Метод Ньютона, или метод касательных основан на вычислении не только значений функции, но и значений ее производной. Разложим f(х) в ряд Тейлора и отбросим члены ряда выше второго порядка:
f (х) = f (х0) + f’ (х0)(х – x0)
В этом приближении корень функции легко найти по формуле:
f (x) = 0, при xi = xi+1 – f (x0)/f ' (x0)
Для нелинейных функций это, конечно, не точное равенство, но способ получить значение, более близкое к корню. Таким образом, метод Ньютона состоит в построении последовательности итераций:
x1 = x0 – f (x0)/ f ' (x0)
x2 = x1 – f (x1)/ f ' (x1)
xi+1 = xi – f (xi)/ f ' (xi)
На какой итерации завершать процесс нахождения корня? Возможно два варианта: либо когда значение функции станет достаточно маленьким по абсолютной величине:
| f (x)| < eps, либо когда практически перестанет меняться значение х:
| f (x)/ f '(x)| < eps
| Xi+1 – Xi| <= eps
3). Метод простой итерации
Рассматриваемый метод реализует третий подход к решению задачи. Предварительно исходное уравнение f(х) = 0 преобразуют к виду φ(х)=х, что является частным случаем более общей структуры g(х)=f(x).Затем выбирают начальное значение х0 и подставляют его в левую часть уравнения, но φ(x)≠х0, поскольку x0 взято произвольно и не является корнем уравнения.
Полученное φ(x)=x1 рассматривают как очередное приближение к корню. Его снова подставляют в правую часть уравнения φ(х1) и получают следующее значение х2 (х2 = φ(x1) и т.д., в общем случае хi+1 =φ(хi). Получающаяся таким образом последовательность х0, x1, х2, х3, х4,… при определенных условиях может сходиться к корню х* (рис. 1.a).
Условие сходимости |φ’(x)| <= 1 на [а,b], причем, чем ближе модуль к нулю, тем выше окажется скорость сходимости к решению. В противном случае последовательность расходится от искомого решения (“метод не сходится”).
На рисунке 2 приведён один из возможных случаев, когда итерационный
процесс не сходится. Видно, что последовательность х0, x1, х2,… удаляется от
корня х*. Это всегда будет иметь место в том случае, если тангенс угла наклона φ(x) в окрестности корня по модулю больше единицы.
Существуют различные способы преобразования уравнения f(x) = 0 к виду φ(x) = x; одни могут привести к выполнению условия сходимости всегда, другие – в отдельных случаях.
Самый простой способ следующий:
f(x) + x = 0 + x, f(x) + x = φ(x)
-
|
|
|
(а)
|
(б)
|
(в)
|
а) 0 < φ’(х) < 1;
|
б) – 1 < φ’(х) < 0
|
|
|
Pис.6
|
|
но он не всегда приводит к успеху. Существует другой способ, в соответствии с которым φ(х)=х-f(х)/к, причем k следует выбирать так, чтобы
|k| >Q/2, где Q=mах |f'(х)| и знак к совпадал бы со знаком f'(х) на [а, b].
Погрешность решения можно оценить из соотношения
|x* - xi| <= (q/(1 – q))*|X(i) – X(i+1)|, где q = max φ(х), на отрезке [a,b].
Вследствие этого для окончания вычислений в методе итераций применят соотношение (q/(q – 1))*|X(i) – X(i + 1)|<= ε, где ε — заданная погрешность решения.
Часто используют упрощенное условие окончания поиска
|X(i) – X(i + 1)|<=ε не вычисляя максимальное значение производной, но в этом случае погрешность решения может не соответствовать заданной (т.е. быть больше или меньше).
4). Метод хорд
В этом методе нелинейная функция f(х) на отделенном интервале [а, b]
заменяется линейной, в качестве которой берется хорда — прямая,
стягивающая концы нелинейной функции. Эта хорда определяется как прямая, проходящая через точки с координатами (а, f(a)) и (b,f(b)). Имея уравнение хорды у = сх + d, можно легко найти точку ее пересечения с горизонтальной осью, подставив в уравнение у = 0 и найдя из него х. Естественно, в полученной таким путем точке x1 не будет решения, ее принимают за новую границу
отрезка, где содержится корень. Через эту точку с координатами (x1, f(x1)) и соответствующую границу предыдущего интервала опять проводят хорду, находят х2 и т.д. несколько раз, получая последовательностьх3 , х4 ,х5,..., сходящуюся к корню.
Метод хорд применим только для монотонных функций.
Алгоритм метода зависит от свойств функции f(х). Если f(b)*f ”(b) > 0, то строящаяся на каждом этапе хорда имеет правый фиксированный ("закрепленный") конец, и алгоритм выглядит следующим образом:
xi+1=xi-(f(xi)/(f(b)-f(xi)))*(b-xi);
при этом последовательность х1 ,х2,,…будет приближаться к корню слева.
Если f(а)f"(а) > 0, то строящаяся на каждом этапе хорда имеет левый фиксированный ("закрепленный") конец, и алгоритм выглядит следующим образом: xi+1 = a +( f(a) / (f(a) – f(xi)))*(xi – a);
|
Рис.7
|
при этом последовательность х1 ,х2,… будет приближаться к корню справа.
На рисунке 7 приведен один из вариантов применения метода хорд. В рассматриваемом случае "закрепленным" является правый конец. Приведено пять шагов (пять хорд), при этом к решению приближаемся слева.
Теоретически доказано, что если первые производные на концах интервала при монотонной и выпуклой функции f(х) не различаются более чем в 2 раза, то справедливо соотношение |х* - хi| < |хi – хi-1| и условием прекращения пополнения последовательности может быть |хi+1 - хi| <= ε, а в качестве корня принято xi+1 (можно также окончить процесс и при достижении f(хi) <= δ, о чем указывалось в концепции методов). На практике указанные условия можно применять и без предварительной проверки производных, отклонение погрешности результата при пологих функциях не будет существенным.
|
|
|
Скачать 2.11 Mb.