Реферат: Решение нелинейных уравнений

Содержание

Введение

1. Теоретическая часть

2. Метод половинного деления

3. Метод хорд

4. Метод Ньютона (касательных)

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

Заключение

Список использованных источников

Введение

Основной цельюреферата является изучение и сравнительныйанализ итерационных методов решения нелинейных алгебраических и трансцендентныхуравнений; реализация этих методов в виде машинных программ на языке высокогоуровня и практическое решение уравнений на ЭВМ.

При разработке алгоритмов, входящих в состав математического обеспечения САПР,часто возникает необходимость в решении нелинейных уравнений вида

f(x) = 0, (1)

где функция f(x)определена и непрерывна на некотором конечном или бесконечном интервале a < x <b. В частности, в форме нелинейныхуравнений представляются математические модели анализа статических свойств объектовпроектирования или их элементов.

1. Теоретическаячасть

Если функция f(x)представляет собой многочлен n-й степени вида

a0 + a1 x + a2 x2 +… +an xn,

то уравнение (1)называется алгебраическим. Когда x находится под знаком трансцендентной функции(показательной, логарифмической, тригонометрической и т.п.), уравнениеназывается трансцендентным. Значение аргумента x*, при котором функция f(x) обращается в нуль, т.е.f(x*) = 0, называется корнем уравнения.

В общем случае дляфункции f(x) не существует аналитических формул для нахождения корней. Болеетого, их точное вычисление не всегда является необходимым. Это объясняется тем,что встречающиеся в инженерной практике уравнения часто содержат коэффициенты,величины которых имеют приближенные значения. В таких случаях решается задачаопределения корней с некоторой заранее заданной степенью точности.

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

1) отделение корней, т.е.нахождение интервалов [a, b], внутри которых содержится один и только одинкорень уравнения;

2) уточнение приближенныхзначений отдельных корней до заданной степени точности.

Этап отделения корнейможет быть выполнен различными способами. Во-первых, приближенное значениекорня иногда бывает известно из физического смысла задачи. Во-вторых, дляотделения корней может использоваться графический способ, основанный напостроении графика функции y = f(x), где приближенные значения действительныхкорней уравнения f(x) = 0 соответствуют абсциссам точек пересечения или касанияграфика с осью 0x (y = 0).

Наиболее частоприменяется метод отделения корней, основанный на следующем положении: если наконцах некоторого интервала [a, b] значения непрерывной функции f(x) имеютразные знаки, т.е. f(a)f(b) < 0, то на этом интервале уравнение (1)имеет хотя бы один корень. При этом корень является единственным, еслипроизводная функции f'(x) существует и сохраняет постоянный знак внутриинтервала [a, b].

Рассмотрим простейшийалгоритм отделения корней нелинейных уравнений, ориентированный наиспользование ЭВМ. Исходный интервал [a, b],на котором определена и непрерывна функция f(x), разбивается на n отрезковравной длины

(x0, x1), (x1, x2), ...,(xn -1, xn),

где x0 < x1< ...< xn и x0 = a,xn = b. Затем вычисляются значения функцииf(xj) в точках xj (j =/>) и выбирается отрезок (xi, xi+1),на концах которого функция имеет разные знаки, т.е. f(xi)f(xi+1) < 0. Если длина этого отрезкадостаточно мала (можно предположить единственность корня), то считается, чтокорень отделен на интервале [a, b], где a = xi, b = xi+1. В противном случаеграницы исходного интервала сдвигаются, т.е. a = xi, b = xi + 1, и процедура повторяется.

Необходимо отметить, чтодлина исходного интервала [a, b], на котором определена функцияf(x), может изменяться в широких пределах. Поэтому число отрезков n, а такжедлина искомого интервала [a, b] являются переменными величинами, которые должнызадаваться в каждом конкретном случае с учетом физического смысла решаемойзадачи.

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

2. Метод половинногоделения

Для этого методасущественно, чтобы функция f(x) была непрерывна и ограничена в заданноминтервале [a, b], внутри которого находится корень. Предполагается также, чтозначения функции на концах интервала f(a) и f(b) имеют разные знаки, т.е.выполняется условие f(a)f(b) < 0.

Обозначим исходныйинтервал [a, b] как [a0, b0]. Для нахождения корня уравнения f(x) = 0 отрезок[a0, b0] делится пополам, т.е. вычисляется начальное приближение x0 = (a0 +b0)/2. Если f(x0) = 0, то значение x0 = x* является корнем уравнения. Впротивном случае выбирается один из отрезков [a0, x0] или [x0, b0], на концахкоторого функция f(x) имеет разные знаки, так как корень лежит в этой половине.Далее выбранный отрезок обозначается как [a1, b1], вновь делится пополам точкойx1 = (a1 + b1)/2 и т.д. В результате на некоторой итерации получается точныйкорень x* уравнения f(x) = 0, либо бесконечная последовательность вложенныхотрезков [a0, b0], [a1, b1], ..., [ai, bi], ..., таких, что f(ai)f(bi) < 0 (i =1, 2, ...), сходящихся к корню x*.

Если требуется определитькорень x* с погрешностью e,то деление исходного интервала [a, b] продолжают до тех пор, пока длина отрезка[ai, bi] не станет меньше 2e, что записывается в форме условия

çbi — ai ç< 2e.

В этом случае серединапоследнего интервала [ai, bi] с требуемой степенью точности дает приближенноезначение корня

x* » (ai + bi) / 2.

Метод половинного делениялегко реализуется на ЭВМ и является наиболее универсальным среди итерационныхметодов уточнения корней. Его применение гарантирует получение решения длялюбой непрерывной функции f(x), если найден интервал, на котором она изменяетзнак. В том случае, когда корни не отделены, будет найден один из корнейуравнения. Метод всегда сходится, но скорость сходимости является небольшой,так как за одну итерацию точность увеличивается примерно в два раза. Поэтому напрактике метод половинного деления обычно применяется для грубого нахождениякорней уравнения, поскольку при повышении требуемой точности значительно возрастаетобъем вычислений.

3. Метод хорд

Пусть дано уравнение f(x)= 0, где f(x) — непрерывная функция, имеющая в интервале (a, b) производныепервого и второго порядков. Корень считается отделенным и находится на отрезке [a,b].

Идея метода хорд состоитв том, что на достаточно малом промежутке [a, b] дугу кривой y = f(x) можнозаменить хордой и в качестве приближенного значения корня принять точкупересечения с осью абсцисс. Рассмотрим случай (рис. 1), когда первая и втораяпроизводные имеют одинаковые знаки, т.е. f '(x)f ²(x) > 0. Тогда уравнение хорды, проходящей через точки A0 и B, имеет вид

/>.

Приближение корня x = x1,для которого y = 0, определяется как

/>.

Аналогично для хорды,проходящей через точки A1 и B, вычисляется следующее приближение корня

/>.

В общем случае формуламетода хорд имеет вид:

/>. (2)

Если первая и вторая производные имеют разные знаки, т.е.

f '(x)f "(x) < 0,

то все приближения ккорню x* выполняются со стороны правой границы отрезка [a, b], как это показанона рис. 2, и вычисляются по формуле:

/>. (3)

Выбор формулы в каждомконкретном случае зависит от вида функции f(x) и осуществляется по правилу:неподвижной является граница отрезка [a, b] изоляции корня, для которой знакфункции совпадает со знаком второй производной. Формула (2) используется в томслучае, когда f(b)f "(b) > 0. Если справедливо неравенство f(a)f"(a) > 0, то целесообразно применять формулу(3).

/>  />

Рис. 1         Рис. 2

/>  />

Рис. 3                                              Рис.4

Итерационный процессметода хорд продолжается до тех пор, пока не будет получен приближенный кореньс заданной степенью точности. При оценке погрешности приближения можнопользоваться соотношением:

/>.

Тогда условие завершениявычислений записывается в виде:

/>, (4)

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

4. Метод Ньютона (касательных)

Пусть уравнение (1) имееткорень на отрезке [a, b], причем f '(x) и f "(x) непрерывны и сохраняютпостоянные знаки на всем интервале [a, b].

Геометрический смыслметода Ньютона состоит в том, что дуга кривой y = f(x) заменяется касательной.Для этого выбирается некоторое начальное приближение корня x0 на интервале [a,b] и проводится касательная в точке C0(x0, f(x0)) к кривой y = f(x) допересечения с осью абсцисс (рис. 3). Уравнение касательной в точке C0 имеет вид

y = f(x0) + f '(x0)×(x — x0).

Далее за приближениекорня принимается абсцисса x1, для которой y = 0:

/>

Затем проводитсякасательная через новую точку C1(x1, f(x1)) и определяется точка x2 еепересечения с осью 0x и т.д. В общем случае формула метода касательных имеетвид:

/>

В результате вычисленийполучается последовательность приближенных значений x1, x2, ..., xi, ...,каждый последующий член которой ближе к корню x*, чем предыдущий. Итерационныйпроцесс обычно прекращается при выполнении условия (4).

Начальное приближение x0должно удовлетворять условию:

f(x0) f ¢¢(x0) > 0. (6)

В противном случаесходимость метода Ньютона не гарантируется, так как касательная будетпересекать ось абсцисс в точке, не принадлежащей отрезку [a, b]. На практике вкачестве начального приближения корня x0, обычно выбирается одна из границинтервала [a, b], т.е. x0 = a или x0 = b, для которой знак функции совпадает сознаком второй производной.

Метод Ньютонаобеспечивает высокую скорость сходимости при решении уравнений, для которыхзначение модуля производной ½f ¢(x)½вблизикорня достаточно велико, т.е. график функции y = f(x) в окрестности корня имеетбольшую крутизну. Если кривая y = f(x) в интервале [a, b] почти горизонтальна,то применять метод касательных не рекомендуется.

Существенным недостаткомрассмотренного метода является необходимость вычисления производных функции дляорганизации итерационного процесса. Если значение f ¢(x) мало изменяется на интервале [a,b], то для упрощения вычислений можно пользоваться формулой

/>, (7)

т.е. значение производнойдостаточно вычислить только один раз в начальной точке. Геометрически этоозначает, что касательные в точках Ci(xi, f(xi)), где i = 1, 2, ..., заменяетсяпрямыми, параллельными касательной, проведенной к кривой y = f(x) в начальнойточке C0(x0, f(x0)), как это показано на рис. 4.

В заключение необходимоотметить, что все изложенное справедливо в том случае, когда начальное приближениеx0 выбрано достаточно близким к истинному корню x* уравнения. Однако это невсегда просто осуществимо. Поэтому метод Ньютона часто используется назавершающей стадии решения уравнений после работы какого-либо надежносходящегося алгоритма, например, метода половинного деления.

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

Чтобы применить этотметод для решения уравнения (1) необходимо преобразовать его к виду />. Далее выбираетсяначальное приближение /> и вычисляется x1, затем x2 и т.д.:

x1 = j(x0); x2 = j(x1); …; xk = j(xk-1); ...

нелинейныйалгебраический уравнение корень

Полученнаяпоследовательность сходится к корню при выполнении следующих условий:

1) функция j(x) дифференцируема на интервале [a,b].

2) во всех точках этогоинтервала j¢(x)удовлетворяет неравенству:

/>   0 £ q £ 1. (8)

При таких условияхскорость сходимости является линейной, а итерации следует выполнять до тех пор,пока не станет справедливым условие:

/>.

Критерий вида

/>,

может использоватьсятолько при 0 £ q £ ½. Иначе итерации заканчиваютсяпреждевременно, не обеспечивая заданную точность. Если вычисление q затруднительно,то можно использовать критерий окончания вида

/>; />.

Возможны различныеспособы преобразования уравнения (1) к виду />. Следует выбирать такой, которыйудовлетворяет условию (8), что порождает сходящийся итерационный процесс, как,например, это показано на рис. 5, 6. В противном случае, в частности, при ½j¢(x)½>1, итерационный процесс расходится и не позволяетполучить решение (рис. 7).

/>

/>

/>

Заключение

Проблема повышениякачества вычислений нелинейных уравнений при помощи разнообразных методов, какнесоответствие между желаемым и действительным, существует и будет существоватьв дальнейшем. Ее решению будет содействовать развитие информационныхтехнологий, которое заключается как в совершенствовании методов организацииинформационных процессов, так и их реализации с помощью конкретных инструментов– сред и языков программирования.

Список использованных источников

1. Алексеев В. Е., Ваулин А.С.,Петрова Г. Б. — Вычислительная техника и программирование. Практикум попрограммированию: Практ.пособие/ -М.: Высш. шк., 1991. — 400 с.

2. Абрамов С.А., Зима Е.В. — Началапрограммирования на языке Паскаль. — М.: Наука, 1987. -112 с.

3. Вычислительная техника ипрограммирование: Учеб. для техн. вузов/ А.В. Петров, В.Е. Алексеев, А.С.Ваулин и др. — М.: Высш. шк., 1990 — 479 с.

4. Гусев В.А., Мордкович А.Г. — Математика: Справ. материалы: Кн. для учащихся. — 2-е изд. — М.: Просвещение,1990. — 416 с.