Методы отделения корней алгебраических и трансцендентных уравнений

Лекция «Приближенные решения алгебраических и трансцендентных уравнений»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

БИК Курс лекций по дисциплине «Численные методы»

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

Раздел 2. Численные методы

2.1.1. Приближенные решения алгебраических и трансцендентных уравнений

Алгебраические и трансцендентные уравнения

Графический метод решения уравнений

1. Алгебраические и трансцендентные уравнения

При решении практических задач часто приходится сталкиваться с решением уравнений. Всякое уравнение с одним неизвестным можно представить в виде

( x )= g ( x ), (1)

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

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

F ( x ) определена и непрерывна на конечном или бесконечном интервале .

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

 Всякое число , обращающее функцию F ( x ) в нуль, т.е. такое, при котором F ( )=0, называется корнем уравнения (1).

 Число называется корнем k -той кратности, если при x =вместе с функцией F ( x ) равны нулю ее производные до ( k -1) порядка включительно:

F ( ) = F / () = … = F ( k -1) ( ) = 0.

Однократный корень называется простым.

 Решить уравнение – значит найти множество всех корней этого уравнения.

Оно может быть конечным или бесконечным.

 Два уравнения F ( x )=0 и G ( x =0) называются равносильными (эквивалентными), если всякое решение каждого из них является решением и для другого, то есть множества решений этих уравнений совпадают.

В зависимости от того, какие функции входят в уравнения (1) или (2), уравнения разделяются на два больших класса: линейные и нелинейные.

Нелинейные уравнения делятся, в свою очередь на: алгебраические и трансцендентные .

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

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

Если функция F ( x ) не является алгебраической, то уравнение (1) называется трансцендентным.

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

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

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

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

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

 Решить уравнение – это значит

установить, имеет ли оно корни,

и найти значение корней с заданной точностью.

 Задача численного нахождения действительных и комплексных корней уравнения (2) обычно состоит из двух этапов:

отделение корней, т.е. нахождение достаточно малых окрестностей рассматриваемой области, в которых находится одно значение корня,

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

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

2. Графические методы решения уравнений

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

Первый способ. Все члены уравнения переносят в левую часть, т. е. представляют его в виде f (х) = 0. После этого строят график функции у = f ( x ), где f (х) – левая часть уравнения. Абсциссы точек пересечения графика функции у = f (х) с осью Ох и являются корнями уравнения, так как в этих точках у = 0 (рис. 1).

Рисунок 1

Второй способ. Все члены уравнения разбивают на две группы, одну из них записывают в левой части уравнения, а другую в правой, т. е. представляют его в виде f (х) = g (х).

После этого строят графики двух функций у = f (х) и у = g (х). Абсциссы точек пересечения графиков этих двух функций и служат корнями данного уравнения. Пусть точка пересечения графиков имеет абсциссу х₀, ординаты обоих графиков в этой точке равны между собой, т. е. f (х₀) = g (х₀). Из этого равенства следует, что х₀ – корень уравнения (рис. 2).

Рисунок 2

Пример 1. Решить графически уравнение х 3 — 2 x 2 + 2х — 1 = 0.

Первый способ. Построим график функции у = х 3 — 2 x 2 + 2х — 1 и определим абсциссы точек пересечения этого графика с осью Ох. Кривая пересекает ось Ох в точке х = 1, следовательно, уравнение имеет один корень (рис. 3). (Отметим, что алгебраическое уравнение третьей степени имеет или один действительный корень или три. Так как кривая пересекает ось абсцисс только в одной точке, то данное уравнение имеет только один действительный корень. Остальные два корня – комплексные.)

Рисунок 3 Рисунок 4

Второй способ. Представим данное уравнение в виде х 3 = 2 x 2 + 2х–1 и построим графики функций у = х 3 и у = 2 x 2 + 2х – 1. Найдем абсциссу точки пересечения этих графиков; получим х = 1 (рис. 4).

Пример 2. Найти приближенно графическим способом корни уравнения lg х — Зх + 5 = 0.

Перепишем уравнение следующим образом: lg х = Зх — 5.

Функции в левой и в правой части уравнения имеют общую область определения: интервал 0

Строим графики функций у = lg х и у = Зх — 5 (рис. 5). Прямая у = Зх-5 пересекает логарифмическую кривую в двух точках с абсциссами x ₁ 0,00001 и x ₂ 1,75. На рисунке трудно показать пересечение графиков этих двух функций в первой точке, однако, учитывая, что нижняя ветвь, логарифмической кривой неограниченно приближается к оси Оу, можно предполагать, что пересечение этих двух графиков произойдет вблизи точки пересечения графика функции у = Зх — 5 и оси Оу. Абсцисса точки пересечения приближенно равна 0,00001. Итак, корни уравнения x ₁ 0,00001 и x ₂ 1,75

Рисунок 5 Рисунок 6

Пример 3. Найти графически корни уравнения 2 х = 2х.

Решение. Строим графики функций у = 2 х и у = 2х. Эти графики пересекаются в двух точках, абсциссы которых равны х ₁ = 1 и х ₂ = 2. Данное урав­нение имеет два корня х ₁ = 1 и х ₂ = 2 (рис. 6).

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

1. Представить указанное уравнение в виде (х) = g (х) с таким расчетом, чтобы функции у=(х) и у = g (х) были просты и удобны для исследования и построения.

2. На бумаге вычертить графики функций у =(х) и у = g (х) в промежутке [а, b ].

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

Первый этап численного решения уравнения (2) состоит в отделении корней, т.е. в установлении “тесных” промежутков, содержащих только один корень.

 Корень уравнения f (х) = 0 считается отделенным на отрезке [ a , b ] , если на этом отрезке уравнение f (х) = 0 не имеет других корней.

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

Отделение корней можно произвести двумя способами – графическим и аналитическим.

Графический метод отделения корней. При графическом методе отделения корней поступают так же, как и при графическом методе решения уравнений.

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

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

Сформулируем без доказательства теоремы, знание которых необходимо при отделении корней.

1) Если непрерывная на отрезке функция F ( x ) принимает на его концах значения разных знаков, то уравнение (2) имеет на этом отрезке, по меньшей мере, один корень

2) Если функция F ( x ) к тому же еще и строго монотонна, то корень на отрезке единственный.

Рассмотрим примеры поведения некоторых функций:

Рисунок 7

Для отделения корней можно эффективно использовать ЭВМ.

Пусть имеется уравнение F ( x )=0, причем можно считать, что все корни находятся на отрезке , в которой функция F ( x ) отделена, непрерывна и F ( A )* F ( B ) F ( x ), начиная с точки X = A , двигаясь вправо с некоторым шагом h .

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

Схема соответствующего алгоритма изображена ниже. Результатом решения поставленной задачи будут выводимые на дисплей в цикле значения параметров X ₁ и X ₂ (Концов выделенных отрезков).

Реферат: Приближенное решение алгебраических и трансцендентных уравнений Метод Ньютона

Пензенский государственный университет

Кафедра «Высшая и прикладная математика»

По курсу «Математический анализ»

на тему «Приближенное решение алгебраических и трансцендентных уравнений. Метод Ньютона»

Выполнил: студент группы 08ВВ1

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

Руденко Алевтина Кирилловна

Биография Исаака Ньютона

Исаак Ньютон, сын мелкого, но зажиточного фермера, родился в деревне Вулсторп (графство Линкольншир), в год смерти Галилея и в канун гражданской войны. Отец Ньютона не дожил до рождения сына. Мальчик родился болезненным, до срока, но всё же выжил и прожил 84 года. Факт рождения под Рождество Ньютон считал особым знаком судьбы.

Покровителем мальчика стал его дядя по матери, Вильям Эйскоу. В детстве Ньютон, по отзывам современников, был замкнут и обособлен, любил читать и мастерить технические игрушки: часы, мельницу и т. п. По окончании школы (1661) он поступил в Тринити-колледж (Колледж святой Троицы) Кембриджского университета. Уже тогда сложился его могучий характер — научная дотошность, стремление дойти до сути, нетерпимость к обману и угнетению, равнодушие к публичной славе.

Научной опорой и вдохновителями творчества Ньютона в наибольшей степени были физики: Галилей, Декарт и Кеплер. Ньютон завершил их труды, объединив в универсальную систему мира. Меньшее, но существенное влияние оказали другие математики и физики: Евклид, Ферма, Гюйгенс, Валлис и его непосредственный учитель Барроу.

Похоже на то, что значительную часть своих математических открытий Ньютон сделал ещё студентом, в «чумные годы» 1664—1666. В 23 года он уже свободно владел методами дифференциального и интегрального исчислений, включая разложение функций в ряды и то, что впоследствии было названо формулой Ньютона-Лейбница. Тогда же, по его утверждению [2], он открыл закон всемирного тяготения, точнее, убедился, что этот закон следует из третьего закона Кеплера. Кроме того, Ньютон в эти годы доказал, что белый цвет есть смесь цветов, вывел формулу «бинома Ньютона» для произвольного рационального показателя (включая отрицательные), и др.

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

1667: эпидемия чумы отступает, и Ньютон возвращается в Кембридж. Избран членом Тринити-колледжа, а в 1668 году становится магистром.

В 1669 году Ньютон избирается профессором математики, преемником Барроу. Барроу пересылает в Лондон сочинение Ньютона «Анализ с помощью уравнений с бесконечным числом членов», содержавшее сжатое изложение некоторых наиболее важных его открытий в анализе. «Анализ» получил некоторую известность в Англии и за её пределами. Ньютон готовит полный вариант этой работы, но найти издателя так и не удаётся. Она была опубликована лишь в 1711 году.

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

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

Разгорается полемика по поводу природы света с Гуком, Гюйгенсом и другими. Ньютон даёт зарок на будущее: не ввязываться в научные споры. В письмах он жалуется, что поставлен перед выбором: либо не публиковать свои открытия, либо тратить всё время и все силы на отражение недружелюбной дилетантской критики. Судя по всему, он выбрал первый вариант.

1680: Ньютон получает письмо Гука с формулировкой закона всемирного тяготения, послужившее, по признанию первого, поводом его работ по определению планетных движений (правда, потом отложенных на некоторое время), составивших предмет «Начал». Впоследствии Ньютон по каким-то причинам, быть может, подозревая Гука в незаконном заимствовании каких-то более ранних результатов самого Ньютона, не желает признавать здесь никаких заслуг Гука, но потом соглашается это сделать, хотя и довольно неохотно и не полностью [3].

1684—1686: после долгих уговоров Ньютон соглашается опубликовать свои главные достижения. Работа над «Математическими началами натуральной философии» (весь трёхтомник издан в 1687 году). Приходят всемирная слава и ожесточённая критика картезианцев: закон всемирного тяготения вводит дальнодействие, несовместимое с принципами Декарта.

В 1689 году Ньютон был в первый раз избран в парламент от Кембриджского университета и заседал там немногим более года. Второе избрание состоялось в 1701—1702 годах.

1696: Королевским указом Ньютон назначен смотрителем Монетного двора (с 1699 года — директор). Он энергично проводит денежную реформу, восстанавливая доверие к основательно запущенной его предшественниками монетной системе Великобритании.

1699: начало открытого приоритетного спора с Лейбницем, в который были вовлечены даже царствующие особы. Эта нелепая распря двух гениев дорого обошлась науке — английская математическая школа вскоре увяла на целый век, а европейская — проигнорировала многие выдающиеся идеи Ньютона, переоткрыв их много позднее. На континенте Ньютона обвиняли в краже результатов Гука, Лейбница и астронома Флемстида, а также в ереси. Конфликт не погасила даже смерть Лейбница (1716).

В 1703 году Ньютон был избран президентом Королевского общества и управлял им до конца жизни — более двадцати лет.

1705: королева Анна возводит Ньютона в рыцарское достоинство. Отныне он сэр Исаак Ньютон. Впервые в английской истории звание рыцаря присвоено за научные заслуги.

Последние годы жизни Ньютон посвятил написанию «Хронологии древних царств», которой занимался около 40 лет, и подготовкой третьего издания «Начал».

В 1725 году здоровье Ньютона начало заметно ухудшаться (каменная болезнь), и он переселился в Кенсингтон неподалёку от Лондона, где и скончался ночью, во сне, 20 (31) марта 1727 года. Похоронен в Вестминстерском аббатстве.

Надпись на могиле Ньютона гласит:

«Здесь покоится сэр Исаак Ньютон, дворянин, который почти божественным разумом первый доказал с факелом математики движение планет, пути комет и приливы океанов.

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

Пусть смертные радуются, что существовало такое украшение рода человеческого»

На статуе, воздвигнутой Ньютону в 1755 г. в Тринити-колледже, высечены стихи из Лукреция:

«Qui genus humanum ingenio superavit (Разумом он превосходил род человеческий)»

Сам Ньютон оценивал свои достижения более скромно:

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

По словам А. Эйнштейна, «Ньютон был первым, кто попытался сформулировать элементарные законы, которые определяют временной ход широкого класса процессов в природе с высокой степенью полноты и точности» и «… оказал своими трудами глубокое и сильное влияние на всё мировоззрение в целом».

История метода

Метод был описан Исааком Ньютоном в рукописи «De analysi per aequationes numero terminorum infinitas» (лат. Об анализе уравнениями бесконечных рядов), адресованной в 1669 году Барроу, и в работе «De metodis fluxionum et serierum infinitarum» (лат. Метод флюксий и бесконечные ряды) или «Geometria analytica» (лат. Аналитическая геометрия) в собраниях трудов Ньютона, которая была написана в 1671 году. В своих работах Ньютон вводит такие понятия, как разложение функции в ряд, бесконечно малые и флюксии (производные в нынешнем понимании). Указанные работы были изданы значительно позднее: первая вышла в свет в 1711 году благодаря Уильяму Джонсону, вторая была издана Джоном Кользоном в 1736 году уже после смерти создателя. Однако описание метода существенно отличалось от его нынешнего изложения: Ньютон применял свой метод исключительно к полиномам. Он вычислял не последовательные приближения xn, а последовательность полиномов и в результате получал приближённое решение x.

Впервые метод был опубликован в трактате «Алгебра» Джона Валлиса в 1685 году, по просьбе которого он был кратко описан самим Ньютоном. В 1690 году Джозеф Рафсон опубликовал упрощённое описание в работе Analysis aequationum universalis (лат. Общий анализ уравнений). Рафсон рассматривал метод Ньютона как чисто алгебраический и ограничил его применение полиномами, однако при этом он описал метод на основе последовательных приближений xn вместо более трудной для понимания последовательности полиномов, использованной Ньютоном. Наконец, в 1740 году метод Ньютона был описан Томасом Симпсоном как итеративный метод первого порядка решения нелинейных уравнений с использованием производной в том виде, в котором он излагается здесь. В той же публикации Симпсон обобщил метод на случай системы из двух уравнений и отметил, что метод Ньютона также может быть применён для решения задач оптимизации путём нахождения нуля производной или градиента.

В 1879 годуАртурКэливработе The Newton-Fourier imaginary problem (англ. Проблема комплексных чисел Ньютона-Фурье) был первым, кто отметил трудности в обобщении метода Ньютона на случай мнимых корней полиномов степени выше второй и комплексных начальных приближений. Эта работа открыла путь к изучению теории фракталов.

Отделение корней

Во многих приближённых методах нахождения корня уравнения заранее требуется знать какой-либо отрезок, на котором лежит искомый корень, и притом только один этот корень (то есть предъявляемый отрезок не должен содержать других корней уравнения). В этом случае говорят, что корень отделён на отрезке. Отделить корень — значит указать такой отрезок, на котором корень отделён. Заметим, что отделить корень можно не единственным образом: если корень отделён на каком-либо отрезке, то годится и любой меньший отрезок, содержащий этот корень. Вообще говоря, чем меньше отрезок, тем лучше, но при этом не следует забывать о том, что на отделение корня на меньших отрезках также тратятся вычислительные усилия, и, быть может, весьма значительные. Таким образом, часто для начала довольствуются весьма широким отрезком, на котором корень отделён.

Кроме того, часто нужно знать начальное приближениеx 0 к корню (который, заметим, неизвестен). В качестве этого начального приближения берут, как правило, любую точку отрезка, на котором отделён корень, например, его середину, если описание метода не предписывает поступить как-нибудь иначе.

Приведём некоторые утверждения, которые могут помочь при отделении корня.

Теорема 1 Если функция непрерывна на отрезке, причём значения её в концах отрезка и — это числа разных знаков, то на отрезке лежит по крайней мере один корень уравнения.

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

Теорема 2 Если функция строго монотонна на отрезке, то есть возрастает или убывает на, то на этом отрезке уравнение не может иметь более одного корня.

Доказательство сразу следует из того, что строго монотонная функция принимает каждое своё значение ровно один раз. Если 0 является значением функции, то и значение 0 принимается один раз, то есть уравнение имеет один корень.

Тем самым, если отрезок, на котором заведомо имеется хотя бы один корень (например, если и — разного знака), — это отрезок строгой монотонности функции, то на отделён ровно один корень.

Заметим, что интервалы монотонности функции можно отыскивать, решая неравенства (что соответствует возрастанию функции) и (что соответствует убыванию).

Описание метода Ньютона (метода касательных)

Пусть корень уравнения f ( x ) = 0 отделён на отрезке, причем f ’( x ) и f ’’( x ) непрерывны и сохраняют определённые знаки при . Найдя какое-нибудь n-e приближение корня n (), мы можем уточнить его по Методу Ньютона следующим образом. Пусть , где hn малая величина. Отсюда, применяя формулу Тейлора, получим:

Внеся эту поправку в формулу (2), получим следующее по порядку приближение корня:

(n=0,1,2…).

Геометрически метод Ньютона эквивалентен замене небольшой дуги кривой y = f ( x ) касательной, проведенной в некоторой точке кривой. в самом деле, положим для определённости, что f ’’( x )> 0 при и f ( b )> 0 (рис. 1).

Выберем, например, х0=b, для которого f ( x ) f ’’( x )> 0. Проведем касательную к кривойy = f ( x ) в точке B0 (x0, f(x0)).

В качестве 1-го приближения x 1 корня возьмем абсциссу точки пересечения этой касательной с осью Ox . Через точку B1( x 1, f ( x 1)) снова проведем касательную, абсцисса точки пересечения которой с Ox даст нам 2-е приближениеx 2 корня и т.д. (рис. 1). Очевидно, что уравнение касательной в точке Bn (xn , f ( xn )) (где n=0,1,2…) есть

.

Заметим, что если в нашем случае положить х0=a и, следовательно, f ( x ) f ’’( x ) 0, f ‘(x) >0, f ’’( x )> 0 при (остальные случаи рассматриваются аналогично). Согласно неравенству (4) имеем f(x0) >0 (например, можно принять х0 = b).

Методом математической индукции докажем, что все приближения xn>(n = 0, 1, 2. ) и, следовательно, f ( xn )> 0. В самом деле, прежде всего, x0 >.

Пусть теперь xn>. Положим

Применяя формулу Тейлора, получим:

где 0, то имеем:

что и требовалось доказать.

Из формулы (3), учитывая знаки f(xn) и f’(х n ), имеем хn+1 0 при , f»(x )>0 и х0 = с, где .

Если f (с) = 0 , то корень = с и задача, таким образом, решена.

Если f ( c ) > 0, то справедливо приведенное выше рассуждение и процесс Ньютона с начальным значением с сходится к корню .

Кроме того, из условия f»(x) >0 вытекает, что f ’ (х) — возрастающая функция и, значит, f ’( x ) > f ‘ (а) > 0 при х>а. Следовательно, х1 можно принять за начальное значение для процесса Ньютона, сходящегося к некоторому корню функции f ( x ) такому, что > с а. Так как в силу положительности производной f ‘ (х) при х > а функция f ( x ) имеет единственный корень на интервале (а, +), то =.

Аналогичное рассмотрение можно провести для других комбинаций знаков производных f ’( x ) и f»(x).

Замечание 2 . Из формулы (3) видно, что чем больше численное значение производной f ’( x ) в окрестности данного корня, тем меньше поправка, которую нужно прибавить к n-му приближению, чтобы получить (n+l)-e приближение. Поэтому метод Ньютона особенно удобно применять тогда, когда в окрестности данного корня график функции имеет большую крутизну. Но если численное значение производной f ’( x ) близ корня мало, то поправки будут велики, и вычисление корня по этому методу может оказаться очень долгим, а иногда и вовсе невозможным. Следовательно, если кривая y = f ( x ) вблизи точки пересечения с осью Ох почти горизонтальна, то применять метод Ньютона для решения уравнения f ( x ) = 0 не рекомендуется.

Оценка погрешности

Для оценки погрешности n-го приближения хn можно воспользоваться общей формулой.

(6)

где m1 — наименьшее значение |f ’( x ) |на отрезке [а, b].

Выведем еще одну формулу для оценки точности приближения xn. Применяя формулу Тейлора, имеем:

(7)

где .Так как в силу определения приближения хп имеем

то из (7) находим:

где М2 — наибольшее значение | f » (х) |на отрезке [а, b].Следовательно, на основании формулы (6) окончательно получаем:

Если процесс Ньютона сходится, то хп- хп-1 0 при п —►. Поэтому при п имеем:

т.е. «установившиеся» начальные десятичные знаки приближений xn -1 иxn начиная с некоторого приближения, являются верными.

Заметим, что в общем случае совпадение с точностью до е двух последовательных приближений хп-1 и хп вовсе не гарантирует, что с той же точностью совпадает значение хп и точный корень | (рис. 19).

Установим также формулу, связывающую абсолютные погрешности двух последовательных приближений хп и xn +1 . Из формулы (5) получаем:

где . Отсюда, учитывая формулу (3), будем иметь:

(9)

Формула (9) обеспечивает быструю сходимость процесса Ньютона, если начальное приближение х0 таково, что

В частности, если

то из формулы (9) получаем:

т.е. в этом случае, если приближение хп имело mверных десятичных знаков после запятой, то следующее приближение хп+1 будет иметь по меньшей мере 2т верных знаков; иными словами, если , то с помощью метода Ньютона число верных знаков после запятой искомого корня удваивается на каждом шаге.

Информация о предыдущих приближениях корня используется для нахождения последующих приближений не только в методе касательных. В качестве примера другого такого метода мы приведём метод, основанный на нахождении xi + 1 по двум предыдущим приближениям xi и xi − 1 с помощью линейной интерполяции, называемый методом хорд .

Идея метода состоит в том, что по двум точкам Mi − 1(xi − 1;f (xi − 1)) и Mi (xi ;f (xi )) построить прямую Mi − 1Mi (то есть хорду, соединяющую две точки графика y = f (x )) и взять в качестве следующего приближения xi + 1 абсциссу точки пересечения этой прямой с осью Ox . Иными словами, приближённо заменить на этом шаге функцию f (x ) её линейной интерполяцией, найденной по двум значениям : x и xi − 1. (Линейной интерполяцией функции f (x ) назовём такую линейную функцию , значения которой совпадают со значениями f (x ) в двух фиксированных точках, в данном случае — в точках xi − 1 и xi .)

Уравнение хорды — это уравнение прямой, проходящей через две точки (a, f(a)) и (b, f(b)).

В зависимости от того, лежат ли точки xi − 1 и xi по разные стороны от корня x * или же по одну и ту же сторону, получаем такие чертежи:

Рис 3. Построение последовательного приближения по методу хорд: два случая.

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

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

построенному для отрезка между xi − 1 и xi , график которой проходит через точку Mi :

Решая уравнение , находим

(1)

Заметим, что величина ki может рассматриваться как разностное приближение для производной f ‘(x ) в точке xi . Тем самым полученная формула (1) — это разностный аналог итерационной формулы метода Ньютона. Вычисление по формуле (1) гораздо предпочтительнее вычисления по другой полученной нами формуле

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

Погрешность

Имеются две разновидности применения формулы (1). Первая разновидность: вычисления ведутся непосредственно по формуле (1) при , начиная с двух приближений x 0 и x 1, взятых, по возможности, поближе к корню x * . При этом не предполагается, что x * лежит между x 0 и x 1 (и что значения функции f в точках x 0 и x 1 имеют разные знаки). При этом не гарантируется, что корень попадёт на отрезок между xi − 1 и xi на каком-либо следующем шаге (хотя это и исключено). В таком случае затруднительно дать оценку погрешности, с которой xi + 1 приближает истинное значение корня x * , и поэтому довольствуются таким эмпирическим правилом: вычисления прекращают, когда будет выполнено неравенство , где — желаемая точность нахождения корня. При этом полагают приближённое значение корня равным .

Условие сходимости

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

где . Таким образом, угловой коэффициент K не должен быть слишком мал по абсолютной величине: при малом угловом коэффициенте уже на первом шаге точка X[1] может выскочить из рассматриваемой окрестности корня X[*] , и сходимость итераций к корню может быть нарушена.

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

Снова предположим, что корень отделён на отрезке и знаки и различны (функция меняет знак при переходе через корень ).

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

Далее повторим процесс для отрезка : снова отыщем его середину , найдём значение функции и сравним знак этого числа со знаком ; если знаки разные, то корень отделён на , если одинаковые, то на (или же оказывается, что ; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.

Рис 4. Последовательное деление отрезка пополам и приближение к корню

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

Погрешность

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

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

Метод легко реализуется на ЭВМ.

Пример решения уравнения методом Ньютона

, .

f ’( x )=

f’(x) 0 при

Вывод: в третьем приближении получен результат с 4-мя точными знаками после запятой: .

Ответ:

Список литературы

· «Основы вычислительной математики», Б. П. Демидович, И.А. Марон, 1966г.

Решение алгебраических и трансцендентных уравнений

Составитель: Панкратов Ю.M.

Лабораторная работа №3

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

1. Теоретические сведения

1.1. Отделение корней

Отыскание приближенных значений корней уравнений состоит из двух этапов – отделение корней и их уточнение с заданной степенью точности. Отделение корней представляет процедуру по разбиению всей области числовой оси на интервалы, в каждом из которых содержится один корень, и ее можно выполнить двумя способами – графическим и аналитическим. При графическом методе строят график функции, который позволяет легко находить отрезки, заключающие в себе только один корень. При аналитическом методе корни уравнения f(x)=0 можно отделить, используя следующую теорему:

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

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

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

2. Под этим графиком в том же масштабе по оси абсцисс построить график первой производной f’(x).

3. Проанализировав эти графики с учетом вышеизложенной теоремы, уже можно, хотя и довольно грубо, указать границы интервалов [a_i ,b_i] для каждого i-го корня.

4. Более наглядно и точнее эту задачу можно решить, если построить еще один совмещенный график сигналов функции f(x) и ее первой производной f’(x). Например, сигнал значений функции f(x) принять равным 1.5, сигнал значений первой производной f’(x) принять равным 1 (чтобы не сливались при совпадении). Функции этих сигналов можно вычислить как

sf(x):=1.5 sign(f(x) — для функции f(x);

sf1(x):= sign(f1(x) — для первой производной f’(x), где f1(x) — первая производная f’(x).

При выборе границ интервалов [a_i ,b_i] для каждого корня надо учитывать, что они не должны совпадать или даже близко приближаться к точкам экстремумов функции f(x) или, что то же самое, к значениям x , при которых f’(x)=0. В этих областях для некоторых методов уточнения корней сходимость итерационных процессов в выбранном интервале [a_i ,b_i] не гарантирована.

1.2. Уточнение корней

В работе рассматриваются только четыре метода уточнения корней. Считаем, что абсциссы x_a и x_b границ интервала [a_i ,b_i] , содержащего единственный корень, известны.

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

1. Вычисляют абсциссу x_c средней точки, делящей отрезок [a_i ,b_i] пополам (Рис.1.) x_c = (x_a+x_b)/2 ;

2. Вычисляют значение функции f(x_c) в средней точке;

3. Если f(x_c)× f(x_b) > 0 , то отрезок [x_c , x_b] можно отбросить, как не содержащий корня, выполнив присвоение x_b= x_c (на рис.1 функция для этого случая показана сплошной линией). Таким образом, правая граница будет смещена влево на половину интервала. В противном случае отбрасывают отрезок [x_a , x_c] с помощью присвоения x_a= x_c (на рис.1 функция для этого случая показана штриховой линией).

4. Если |x_b — x_a| > e , то цикл повторяют, начиная с п.1, в противном случае считают, что найденное значение и есть корень уравнения этого интервала, вычисленный с точностью e.

Достоинства метода: простота алгоритма, высокая надежность отыскания корня. Недостаток – большое количество шагов итераций.

1. Одну из граничных точек принимают за неподвижную точку x_c . Обычно это точка, в которой знак функции совпадает со знаком второй производной, т.е. f(x_c)× f’’(x_c) > 0. Тогда вторую граничную точку принимают за начальное приближение x₀ (Рис.2.) ;

2. Каждое следующее значение абсциссы x_i+1 вычисляют как точку пересечения хорды, соединяющей неподвижную точку x_c и крайнюю текущую точку кривой x_i , с осью абсцисс по формуле:

3. Если |x_i+1 – x_i | > e , то цикл повторяют, начиная с п.2, в противном случае считают, что найденное значение и есть корень уравнения этого интервала, вычисленный с точностью e.

Метод обладает теми же достоинствами и недостатками, как и предыдущий.

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

1. За начальное приближение x₀ принимают граничную точку, в которой знак функции совпадает со знаком второй производной, т.е. f(x₀)×f’’(x₀)> 0 (Рис.3.) ;

2. Каждое следующее значение абсциссы x_i+1 вычисляют как точку пересечения касательной, проведенной в текущей точкой кривой x_i , с осью абсцисс по формуле:

3. Если |x_i+1 – x_i | > e , то цикл повторяют, начиная с п.2, в противном случае считают, что найденное значение и есть корень уравнения этого интервала, вычисленный с точностью e.

Достоинства метода: простота алгоритма, высокая скорость сходимости. Недостатки: необходимость отыскания первой производной в аналитической форме, ненадежность отыскания корня в указанном диапазоне. На рис.3 показано, что в случае проведения касательной в точке b , она может пересечься с осью x в точке c, лежащей за пределами выбранного интервала [a,b], и корень может быть найден совсем в другом интервале.

1.2.4. Метод итераций

1. Исходное уравнение f(x)=0 преобразуют к виду: x=F(x) (1)

2. Левая часть этого уравнения представляет уравнение прямой линии, проходящей через начало координат под углом в 45° к оси x. Абсцисса пересечения этой прямой с функцией F(x)и представляет корень уравнения f(x)=0(Рис.4.).

3. Задают начальное приближение x₀ и вычисляют значение функции F(x₀) (см.рис.4а). Из (1) следует, что его можно принять за первое приближение x₁ : x₁=F(x₀).

4. Вычислив функцию F(x₁) , принимают это значение за второе приближение x₂=F(x₁) и так далее. В общем случае для (i+1)-й итерации можно записать:

5. Итерации повторяют, пока выполняется условие |x_i+1 – x_i | > e .

Геометрическая интерпретация метода показана на рис.4, причем на рис.4а) и 4б) процесс сходится к корню уравнения f(x)=0, а на рис.4в) и 4г) – расходится, хотя начальное приближение x₀ и выбрано для них ближе к корню. Из рис.4а) можно заметить, что угол наклона касательной к любой точке кривой y=F(x) не превышает 45° к оси x , т.е. F’(x) -1. На рис.4в) и 4г) это условие не соблюдается и итерационный процесс на них расходится от корня уравнения. Отсюда следует, что для обеспечения сходимости итерационного процесса должно соблюдаться условие:

Оба этих решения можно записать как: -2 0 при f’(x) 3 +cos(x)-0.2=017.15cos(x-0.1)+0.4x 3 =025.x 4 +(10-x) 3 +x-600=02.x 3 +(8-x) 2 -60=010.3cos(x-0.5)+0.4x 2 =018.sin(x)+0.2x 2 =026.sin(x)+cos(2x)+0.8x-3=03.0.2x 2 +3sin(x)+1=011.0.01x 4 -2(x-5) 2 -25x=019.(12-sin(x)) 2 -x 2 -134=027.0.04x 3 +2(x-4) 2 -2x-5=04.x 3 -15(x-5)+1=012.5(x-4) 4 +10(x-5) 3 +x 2 =020.x 4 -x 3 +x 2 -5=028.4sin(x)-x 2 +0.2=05.20cos(x)+x 3 -10=013.sin(x 2 )+5(x+8)-2=021.x 4 +x 3 -x 2 -5=029.sin(x 2 )+x+2=06.20cos 2 (x)+x 3 -10=014.8sin(x)+2x 2 -4=022.8cos(x)+x 2 -4=030.24cos(x-1)+sin(x)+10x-25=07.2cos(x-5)+(x-8) 2 -2=015.40cos(x-5)+(x-8) 3 -2=023.5cos(x)+(x-4) 2 -3=031.10cos(x)+5sin(x)+4x-10=08.10sin(x)+4x-15=016.2sin(x)-x+0.2=024.5cos(x)+(x-8) 2 -7=032.8cos(x 2 )+(x-2) 3 +5x-3=0

Отчет по работе должен включать:

2.1. Отделение корней, для чего необходимо построить графики функции f(x) , ее первой производной f’(x) и график сигналов.

2.2. Уточнение корней методами половинного деления, хорд, касательных и итераций.

2.3. Проверку результатов с помощью встроенной функции root.

3. Пример выполнения задания

1. Бахвалов Н.С. Численные методы. – М., Наука,1975. –632 c.

2. Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы. – М., Наука,1976. –304 с.

3. Волков Е.А. Численные методы : Учебное пособие для вузов. – 2-е изд. – М., Наука, 1987.

4. Копченова Н.В., Марон И.А. Вычислительная математика в примерах и задачах. – М., Наука,1972.

5. Турчак Л.И., Плотников П.В. Основы численных методов: Учеб. пособие.– 2-ое изд., перераб. и доп. -М.: ФИЗМАТЛИТ, 2002. –304 c.

6. Исаков В.Н. Элементы численных методов. – М., Издательский центр «Академия»,2003. –192 c.