Методы решения нелинейных уравнений введение

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

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

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

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

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

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

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

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

где функция f(x) определена и непрерывна на некотором конечном или бесконечном интервале a 0. Тогда уравнение хорды, проходящей через точки A0 и B, имеет вид

.

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

.

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

.

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

. (2)

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

f ‘(x)f «(x) 0. Если справедливо неравенство f(a)f «(a) >0, то целесообразно применять формулу (3).

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

.

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

, (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 должно удовлетворять условию:

В противном случае сходимость метода Ньютона не гарантируется, так как касательная будет пересекать ось абсцисс в точке, не принадлежащей отрезку [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).

Рис. 5

Рис. 6

Рис. 7

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

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

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

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

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

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

Численные методы решения нелинейных уравнений

Если законы функционирования модели нелинейны, а моделируемые процесс или система обладают одной степенью свободы (т.е. имеют одну независимую переменную), то такая модель, как правило, описывается одним нелинейным уравнением.

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

Дано нелинейное уравнение:

( 4.1)

Необходимо решить это уравнение, т. е. найти его корень .

Если функция имеет вид многочлена степени m,

где a_i — коэффициенты многочлена, , то уравнение f(x)=0 имеет m корней (рис. 4.2).

Если функция f(x) включает в себя тригонометрические или экспоненциальные функции от некоторого аргумента x , то уравнение (4.1) называется трансцендентным уравнением .

Такие уравнения обычно имеют бесконечное множество решений.

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

Доказано также, что нельзя построить формулу, по которой можно было бы решать произвольные алгебраические уравнения степени, выше четвертой.

Однако точное решение уравнения не всегда является необходимым. Задачу отыскания корней уравнения можно считать практически решенной, если мы сумеем найти корни уравнения с заданной степенью точности . Для этого используются приближенные (численные) методы решения.

Большинство употребляющихся приближенных методов решения уравнений являются, по существу, способами уточнения корней. Для их применения необходимо знание интервала изоляции [a,b] , в котором лежит уточняемый корень уравнения (рис. 4.3).

Процесс определения интервала изоляции [a,b] , содержащего только один из корней уравнения, называется отделением этого корня.

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

Процесс определения корней алгебраических и трансцендентных уравнений состоит из 2 этапов:

1. отделение корней, — т.е. определение интервалов изоляции [a,b] , внутри которого лежит каждый корень уравнения;
2. уточнение корней, — т.е. сужение интервала [a,b] до величины равной заданной степени точности .

Для алгебраических и трансцендентных уравнений пригодны одни и те же методы уточнения приближенных значений действительных корней:

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

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

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

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

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

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

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

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

где функция f(x) определена и непрерывна на некотором конечном или бесконечном интервале a 0. Тогда уравнение хорды, проходящей через точки A0 и B, имеет вид

.

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

.

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

.

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

. (2)

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

f ‘(x)f «(x) 0. Если справедливо неравенство f(a)f «(a) > 0, то целесообразно применять формулу (3).

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

.

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

, (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 с.