Решение нелинейных и трансцендентных уравнений методом секущих

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Санкт-Петербургский государственный университет аэрокосмического приборостроения»

Кафедра вычислительных машин и комплексов

Курсовая работа (проект) защищена с оценкой руководитель

Пояснительная записка к курсовой работе (проекту)

Решение нелинейных и трансцендентных уравнений методом секущих

По дисциплине: информатика

Санкт-Петербург 2012

Оглавление

1. Задание на проектирование

2. Анализ, формальная постановка и описание метода решения

2.1 Нелинейные и трансцендентные уравнения

2.2 Локализация корней

2.3 Уточнение корней

2.4 Методы уточнения корней

2.4.1 Метод половинного деления (бисекции, дихотомии)

2.4.2 Метод хорд

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

2.4.3.1 Сходимость метода Ньютона

2.4.3.2 Выбор начального приближения в методе Ньютона

2.4.4 Модифицированный метод Ньютона

2.4.5 Метод секущих

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

3. Разработка алгоритма решения задачи

4. Реализация разработанного алгоритма

5. Тестирование разработанной программы

5.1 Ручной расчёт тестового примера

5.2 Решение тестовой задачи в MatLab

Список использованной литературы

1. Задание на проектирование

математизация программирование алгоритм локализация

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

Реализуется численное решение нелинейных и трансцендентных уравнений методом секущих.

2. Анализ, формальная постановка и описание метода решения

2.1 Нелинейные и трансцендентные уравнения

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

В общем случае нелинейное уравнение с одним неизвестным можно записать в виде:

, (2.1)

где - некоторая непрерывная функция аргумента x.

Всякое число , обращающее функцию в нуль, т.е. при котором , называется корнем уравнения (2.1). Если в точке наряду с функцией обращаются в ноль и ее производные до порядка включительно, то число называют корнем k-й кратности. Однократный корень также называют простым. В дальнейшем мы будем говорить именно о простых корнях.

В зависимости от вида функции нелинейные уравнения подразделяются на два класса - алгебраические и трансцендентные [1].

Уравнение (2.1) называется алгебраическим, если функция является алгебраической функцией. Алгебраическое уравнение всегда может быть представлено в канонической форме:

, (2.2)

где - коэффициенты уравнения. Показатель n называют степенью алгебраического уравнения.

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

.

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

Однако подавляющее большинство нелинейных уравнений, встречающихся на практике, не удается решить прямыми методами. Даже для алгебраического уравнения выше четвертой степени не удается получить аналитического решения в виде формулы с конечным числом арифметических действий. Во всех таких случаях приходится обращаться к численным методам, позволяющим получить приближенные значения корней с любой заданной точностью [2].

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

2.2 Локализация корней

Для отделения корней уравнения (2.1) необходимо иметь критерий, позволяющий убедится, что, во-первых, на рассматриваемом отрезке имеется корень, а, во-вторых, что этот корень единственный на указанном отрезке. Если функция непрерывна на отрезке , а на концах отрезка её значения имеют разные знаки , то на этом отрезке расположен, по крайней мере, один корень. Это условие (как видно из рисунка 2.1) не обеспечивает единственности корня. Достаточным дополнительным условием, обеспечивающем единственность корня на отрезке является требование монотонности функции на этом отрезке. В качестве признака монотонности функции можно воспользоваться условием знакопостоянства первой производной .

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

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

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

В качестве примера рассмотрим уравнение . Переходя к эквивалентному уравнению построим графики функций и (рис. 2.2)

Размещено на http://www.allbest.ru/

Из графика видно, что уравнение содержит один корень, расположенный в интервале .

Размещено на http://www.allbest.ru/

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

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

Размещено на http://www.allbest.ru/

Предвидя подобные ситуации, следует выбирать достаточно малые значения h.

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

Отделяя таким образом корни, мы, по сути, получаем их приближенные значения с точностью до выбранного шага. Так, например, если в качестве приближенного значения корня взять середину отрезка локализации, то абсолютная погрешность этого значения не будет превосходить половины шага поиска (h/2). Уменьшая шаг в окрестности каждого корня, можно, в принципе, повысить точность отделения корней до любого наперед заданного значения. Однако такой способ требует большого объема вычислений. Поэтому при проведении численных экспериментов с варьированием параметров задачи, когда приходится многократно осуществлять поиск корней, подобный метод не годится для уточнения корней и используется только для отделения (локализации) корней, т.е. определения начальных приближений к ним. Уточнение корней проводится с помощью других, более экономичных методов.

2.3 Уточнение корней

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

.

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

, (2.3)

то говорят, что итерационный процесс сходится.

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

В общем случае это неравенство можно представить в виде:

, (2.4)

где и - некоторые числа, значения которых определяются методом уточнения корня. От значений q и зависит насколько с каждым шагом уменьшается погрешность приближенных значений и, соответственно, насколько быстро можно получить приближенное значение с заданной точностью. Главным показателем скорости сходимости метода является значение , называемое порядком сходимости. При погрешность с каждым шагом убывает линейно, в этом случае говорят о линейной сходимости. Если , то говорят, что имеет место сверхлинейная сходимость.

2.4 Методы уточнения корней

2.4.1 Метод половинного деления (бисекции, дихотомии)

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

Размещено на http://www.allbest.ru/

Затем исследуем значение функции на концах отрезков и . Тот из отрезков, на концах которого принимает значения разных знаков, содержит искомый корень; поэтому его принимаем в качестве нового отрезка (на рис. 2.5 это отрезок ). Вторую половину отрезка , на которой не меняет знак, отбрасываем. В качестве следующего приближения корня принимаем середину нового отрезка и т.д. Таким образом, k-е приближение вычисляется как

. (2.5)

После каждой итерации отрезок, на котором расположен корень, уменьшается вдвое, а после k итераций в раз:

. (2.6)

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

. (2.7)

Поскольку корень принадлежит отрезку , а - середина этого отрезка, то величина всегда будет меньше половины длины отрезка (см. рис. 2.5), т.е.

. (2.8)

Следовательно, условие (2.7) будет выполнено, если

. (2.9)

Таким образом, итерационный процесс нужно продолжать до тех пор, пока не будет выполнено условие (2.9).

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

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

, (2.10)

Вычислим количество итераций N, требуемое для достижения заданной точности . Пользуясь выражением (2.6) можно выяснить для каких значений k будет выполнено условие (2.9), и взять в качестве N наименьшее из таких k:

, , (2.11)

где - целая часть числа x. Например, при и получим .

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

. (2.12)

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

2.4.2 Метод хорд

Рассматриваемый метод так же, как и метод половинного деления, предназначен для уточнения корня на интервале , на концах которого которого функция принимает значения разных знаков.

Размещено на http://www.allbest.ru/

Очередное приближение в отличие от метода половинного деления берем не в середине отрезка, а в точке , где пересекает ось абсцисс прямая линия (хорда), проведенная через точки А и В (рис. 2.6).

Запишем уравнение прямой, проходящей через точки А и В:

.

Для точки пересечения прямой с осью абсцисс () получим уравнение

. (2.13)

В качестве нового интервала для продолжения итерационного процесса выбираем тот из двух и , на концах которого функция принимает значения разных знаков. Для рассматриваемого случая (рис. 2.6) выбираем отрезок , так как . Следующая итерация состоит в определении нового приближения как точки пересечения хорды с осью абсцисс и т.д.

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

(2.14)

Размещено на http://www.allbest.ru/

Замечание. Метод половинного деления и метод хорд очень похожи, в частности, процедурой проверки знаков функции на концах отрезка. При этом второй их них в ряде случаев дает более быструю сходимость итерационного процесса. Однако в некоторых случаях метод хорд может сходится существенно медленнее метода половинного деления. Такая ситуация показана на рис. 2.7. Оба рассмотренных метода не требуют знания дополнительной информации о функции . Например, не требуется, чтобы функция была дифференцируема. Даже для разрывных функций рассмотренные методы обладают гарантированной сходимостью. Более сложные методы уточнения корня используют дополнительную информацию о функции , прежде всего свойство дифференцируемости. Как результат они обычно обладают более быстрой сходимостью, но в то же время, применимы для более узкого класса функций, и их сходимость не всегда гарантирована. Примером такого метода служит метод Ньютона.

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

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

,

выражая отсюда , получим

Размещено на http://www.allbest.ru/

.

Аналогично могут быть найдены и следующие приближения. Формула для k+1-го приближения имеет вид

, (2.15)

Из формулы (2.15) вытекает условие применимости метода: функция должна быть дифференцируемой и в окрестности корня не должна менять знак.

Для окончания итерационного процесса могут быть использованы условия (2.12) или (2.14).

Замечание 1. В методе Ньютона, в отличие от предыдущих методов, не обязательно задавать отрезок , содержащий корень уравнения, а достаточно найти некоторое начальное приближение корня .

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

,

и вместо нелинейного уравнения решим линеаризованное уравнение

рассматривая его решение как следующее (первое) приближение к искомому значению корня. Решение этого уравнение очевидно:

Повторяя это процесс приходим к формуле Ньютона (2.15).

2.4.3.1 Сходимость метода Ньютона

Выясним основные условия сходимости последовательности значений , вычисляемых по формуле (2.15), к корню уравнения (2.1). Предполагая, что дважды непрерывно дифференцируема, разложим в ряд Тейлора в окрестности k-го приближения

.

Разделив последнее соотношение на и перенеся часть слагаемых из левой части в правую, получим:

.

Учитывая, что выражение в квадратных скобках согласно (2.15) равно , переписываем это соотношение в виде

.

Отсюда

. (2.16)

Из (2.16) следует оценка

, (2.17)

где , .

Очевидно, что ошибка убывает, если

. (2.18)

Полученное условие означает, что сходимость зависит от выбора начального приближения.

Оценка (2.17) характеризует скорость убывания погрешности для метода Ньютона: на каждом шаге погрешность пропорциональна квадрату погрешности на предыдущем шаге. Следовательно, метод Ньютона обладает квадратичной сходимостью.

Размещено на http://www.allbest.ru/

2.4.3.2 Выбор начального приближения в методе Ньютона

Как следует из условия (2.18) сходимость итерационной последовательности, получаемой в методе Ньютона, зависит от выбора начального приближения . Это можно заметить и из геометрической интерпретации метода. Так, если в качестве начального приближения взять точку (рис. 2.9), то на сходимость итерационного процесса рассчитывать не приходится.

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

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

2.4.4 Модифицированный метод Ньютона

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

. (2.19)

2.4.5 Метод секущих

Еще одна модификация метода Ньютона связана с приближенным вычисление производной в окрестности точки по формуле

.

Подставляя это выражение в формулу Ньютона (2.15), приходим к формуле

, , (2.20)

которая определяет метод секущих. Название метода связано с его геометрической интерпретацией (см. рис. 2.10).

Секущая, проведенная через точки и , пересекает ось абсцисс в точке , значение которой определяется формулой (2.20).

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

На практике, как правило, поступают следующим образом: нулевое приближение выбирают аналогично выбору начального приближения в методе Ньютона, а в качестве первого приближения выбирают величину , где - заданная погрешность. Эти значения используются для нахождения последующего (второго) приближения по формуле (2.20).

Затем, значения и используют для определения третьего приближения и т.д. Альтернативно, в качестве нулевого и первого приближений могут быть выбраны границы отрезка локализации корня, если они известны. В этом случае первая итерация метода секущий даст результат, аналогичный методу хорд. Для завершения итерационного процесса можно воспользоваться условием (2.14). Метод секущих несколько уступает методу Ньютона в скорости сходимости, однако он не требует вычисления производной и поэтому оказывается особенно полезным в тех случаях, когда получение аналитического выражения для производной затруднено или невозможно, например, если функции получена в ходе численных расчетов, а не задана аналитически.

Размещено на http://www.allbest.ru/

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

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

Теперь рассмотрим более общий итерационный метод уточнения корней. Представим исходное уравнение в виде

. (2.21)

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

, . (2.22)

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

3. Разработка алгоритма решения задачи

Шаг 1 Определяем общую структуру программы

Программа:

Ввести выражения для вычисляемой функции

Ввести a, b, E

Определить X

Вывести X

Конец.

Шаг 2. Детализируем операцию определения X.

c=a-(y/(d-y))*(b-a);

x=c;

g=f(x);

i=1;

Цикл пока

while (1)

i = i+1

если(i == 16)

все если

все цикл

если (y*g)>0

то a=c

иначе b=c;

все цикл

Все.

Таким образом программа состоит из двух простых шагов. Полностью имеет вид:

Программа:

Ввести выражение для вычисляемой функции

Ввести a, b, E

% определить Х.

c=a-(y/(d-y))*(b-a);

x=c;

g=f(x);

i=1;

Цикл-пока

while (1)

i = i+1

если (i == 16)

се если

се цикл

если (y*g)>0

то a=c

иначе b=c;

се цикл

ывести Х

Конец.

Общая схема алгоритма приведена на рисунке 3.1

Размещено на http://www.allbest.ru/

Рис. 3.1 Схема алгоритма программы

Алгоритм подпрограммы ввода границ интервала вычисления приведен на рис. 3.2

Размещено на http://www.allbest.ru/

Рис. 3.2 Ввод границ интервала

4. Реализация разработанного алгоритма

R=input('Введите функцию, f=','s')

f=inline(R);

a=input('Введите нижний промежуток')

b=input('Введите верхий промежуток')

if a>b

disp('Неверный ввод промежутка '), break

else

e=input('Введите относительную погрешность')

c=1

x=a;

y=f(x);

x=b;

d=f(x);

c=a-(y/(d-y))*(b-a);

x=c;

g=f(x);

i=1;

while (1)

i = i+1

if (i == 16) break;

end;

if (y*g)>0

a=c

else

b=c;

end

x=a;

y=f(x);

x=b;

d=f(x);

c=a-(y/(d-y))*(b-a)

x=c;

g=f(x);

end

end

disp('Ваш ответ'),disp(c)

5. Тестирование разработанной программы

5.1 Ручной расчёт тестового примера

В качестве тестового примера возьмём функцию .

на интервале [-2;-1]. Относительная погрешность Е = 0.01. Результаты приведены ниже.

Искомый корень : - 1,6430

5.2 Решение тестовой задачи в MatLab

Программа MatLab при расчёте тестового примера даёт следующие значения:

Введите функцию, f=5^x-3*x-5

R =

5^x-3*x-5

Введите нижний промежуток-2

a = -2

Введите верхий промежуток-1

b = -1

Введите относительную погрешность0.01

e = 0.0100

c = 1

i = 2

c = -1.6429

i = 3

c = -1.6430

i = 4

c = -1.6430

i = 5

c = -1.6430

i = 6

c = -1.6430

i = 7

c = -1.6430

i = 8

c = -1.6430

i = 9

c = -1.6430

i = 10

c = -1.6430

i = 11

c = -1.6430

i = 12

c = -1.6430

i = 13

c = -1.6430

i = 14

c = -1.6430

i = 15

c = -1.6430

i = 16

Ваш ответ

-1.6430

Таким образом, значение ,вычисленное при помощи программы MatLab, равно -1.6430. Следовательно, результаты тестовой задачи совпадают для случаев ручного расчёта и расчёта в MatLab.

математизация matlab трансцендентный локализация

Список использованной литературы

1. Самарский А.А. Введение в численные методы. Учебное пособие для Вузов, - М., Наука,1987,288 с.,;

2. Дьяконов В.П. MatLab 6.5 SP/7 + Simulink 5/6. Основы применения. М.: СОЛОН-Пресс, 2005.

3. Иванов Г.С Основы программирования : Учебник для вузов.- М. : Изд-во МГТУ им. Н.Э.Баумана, 2001

4. Бураков М.В. Основы работы в MATLAB: учебное пособие/ М.В. Бураков .- ГУАП.СПб., 2006;

Размещено на Allbest.ru