Основные теоретические положения

Многие задачи исследования различных объектов с помощью математических моделей, применяемых их для прогноза или расчёта, приводят к необходимости решения нелинейных уравнений.

Уравнения могут быть алгебраическими и трансцендентными. Пример

алгебраического уравнения: y = a + bx + cx², трансцендентного: y = eⁿ + x.

Решить уравнение – это найти такое значение переменной х, при котором заданная функция равна нулю (f (x) = 0).

Как правило, процесс решения нелинейного уравнения обще­го вида f(х)=0 осуществляется в два этапа. На первом этапе от­деляют корни, т.е. находят такие отрезки, внутри которых нахо­дится строго один корень. На втором этапе уточняют корень, т.е. находят его значение х* с предварительно заданной точностью ε. В практических задачах решением называют любое значение х, отличающееся по модулю от точного значения х* не более чем на величину ε.

Рассмотрим следующие методы уточнения корня уравнения:

- метод дихотомии;

- метод касательных;

- метод простой итерации;

- метод хорд.

Метод дихотомии

Пусть функция 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) действительно разных знаков.

Это условие можно записать двумя разными способами:

1. ((f (а) <= 0) and (f (b) > 0)) or ((f (b) <= 0) and (f (a) > 0))

2. f (a) * f(b) <= 0

Если это не так, нужно только напечатать сообщение об ошибке, иначе можно приступать к поиску корня. Поиск проще всего оформить в виде цикла:

Do until (b-а) < eps... loop

Здесь eps - константа, равная, например 10ˉ⁵. На каждой итерации цикла нужно вычислить значение точки с и сравнить знак функции в этой точке со знаком f(а). Если знаки разные, о точке b можно "забыть": b:=с. Иначе – "забываем" о точке а. После окончания цикла остается лишь напечатать найденный корень. Ближе всего к корню будет, середина окончательного отрезка [а,d], длина которого не превышает заданной точности eps.

Метод касательных

Метод Ньютона, или метод касательных основан на вычислении не только значений функции, но и значений ее производной. Разложим f(х) в ряд Тейлора и отбросим члены ряда выше второго порядка:

f (х) = f (х0) + f’ (х₀)(х – x₀)

В этом приближении корень функции легко найти по формуле:

f (x) = 0, при x_i = x_i+1 – f (x₀)/f ' (x₀)

Для нелинейных функций это, конечно, не точное равенство, но способ получить значение, более близкое к корню. Таким образом, метод Ньютона состоит в построении последовательности итераций:

x₁ = x₀ – f (x₀)/ f ' (x₀)

x₂ = x₁ – f (x₁)/ f ' (x₁)

x_i+1 = x_i – f (x_i)/ f ' (x_i)

На какой итерации завершать процесс нахождения корня? Возможно два варианта: либо когда значение функции станет достаточно маленьким по абсолютной величине:

| f (x)| < eps, либо когда практически перестанет меняться значение х:

| f (x)/ f '(x)| < eps

| X_i+1 – X_i| <= eps

Метод простой итерации

Рассматриваемый метод реализует третий подход к решению задачи. Предварительно исходное уравнение f(х) = 0 преобразуют к виду φ(х)=х, что является частным случа­ем более общей структуры g(х)=f(x).Затем выбирают началь­ное значение х₀ и подставляют его в левую часть уравнения, но φ(x)≠х₀, поскольку x₀ взято произвольно и не является корнем уравнения.

Полученное φ(x)=x₁ рассматривают как очередное приближение к корню. Его снова подставляют в правую часть уравнения φ(х₁) и получают следующее значение х₂ (х₂ = φ(x₁) и т.д., в общем случае х_i+1 =φ(х_i). Получающаяся таким образом последовательность х₀, x₁, х₂, х₃, х₄,… при определенных услови­ях может сходиться к корню х^* (рис. 1.a).

Условие сходимости |φ’(x)| <= 1 на [а,b], причем, чем ближе модуль к нулю, тем выше окажется скорость сходимости к решению. В про­тивном случае последовательность расходится от искомого решения (“метод не сходится”).

На рисунке 2 приведён один из возможных случаев, когда итерационный

процесс не сходится. Видно, что последовательность х₀, x₁, х₂,… удаляется от

корня х^*. Это всегда будет иметь место в том случае, если тангенс угла наклона φ(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^* - x_i| <= (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)) и соответствующую границу предыду­щего интервала опять проводят хорду, находят х₂ и т.д. несколько раз, получая последовательностьх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

 

при этом последовательность х₁,х₂,… будет приближаться к корню справа.

На рисунке 7 приведен один из вариантов применения ме­тода хорд. В рассматриваемом случае "закрепленным" является правый конец. При­ведено пять шагов (пять хорд), при этом к решению приближаемся слева.

Теоретически доказано, что если первые производные на кон­цах интервала при монотонной и выпуклой функции f(х) не раз­личаются более чем в 2 раза, то справедливо соотношение |х^* - х_i| < |х_i – х_i-1| и условием прекращения пополнения после­довательности может быть |х_i+1 - х_i| <= ε, а в качестве корня принято x_i+1 (можно также окончить процесс и при достижении f(х_i) <= δ, о чем указывалось в концепции методов). На практике указанные условия можно применять и без предварительной про­верки производных, отклонение погрешности результата при по­логих функциях не будет существенным.

Порядок выполнения работы

1. Получить у преподавателя вариант задания, включающий в себя трансцендентное или алгебраическое уравнение (F(x) = 0), отрезок для поиска решения (a, b), точность вычисления значения корня (eps) и задание, каким из методов (все методы) решить задачу.

2. Исследовать существование корня на заданном отрезке, требования к функции: разные знаки на концах отрезка, непрерывность).

3. Выяснить, с какой стороны отрезка строить приближение к решению уравнения: если знак второй производной совпадает со знаком функции
(f(х)- f"(х) > 0), то приближение строим елевой стороны отрезка, в противном случае - с левой стороны.

4. Написать подпрограмму для вычисления функции F(х).

5. Написать подпрограмму, например для первого метода дихотомии.

6. Написать подпрограмму, например, для второго метода касательных или простой итерации.

7. Найти первую производную функции F(x) и оформить её вычисление процедурой функции (для метода касательных).

8. Найти приведённую функцию и оформить её вычисление процедурой функции.

9. Написать головной модуль.

10. Отладить программу и получить результат.