Графический и аналитический методы отделения корней

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

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

Реферат

Графический и аналитический методы отделения корней

Введение

Все естественные науки используют вычисления в своей практике. Еще в V веке до нашей эры философ Пифагор, которого можно назвать основоположником математической физики, утверждал, что всё сущее управляется числами. Все значительные этапы в развитии физики сопровождались разработкой новых разделов математики. Величайший физик и математик Исаак Ньютон при формулировке основ механики, которые были изложены в его знаменитых «Математических началах натуральной философии», опубликованных в 1687 году, разработал дифференциальное и интегральное исчисление. Примерно 50 лет спустя Леонард Эйлер создал вариационное исчисление, решая актуальные задачи строительной механики. Создание молекулярно-кинетической теории теплоты происходило вместе с развитием теории вероятностей. Классическая электродинамика дала мощный импульс исследованиям дифференциальных уравнений в частных производных. Исследование устойчивости динамических систем привело великого математика и физика Анри Пуанкаре к разработке теории бифуркаций. Квантовая механика базируется на теории операторов в гильбертовом пространстве. Аналогичное влияние решения физических проблем на развитие новых разделов математики наблюдается в областях квантовой хромо динамики, нелинейных колебаний, теории единого поля и т.д. Повсеместное распространение персональных компьютеров обеспечивает широкую доступность численных методов. При этом у начинающих исследователей часто возникают трудности выбора конкретного метода для решения поставленной задачи. Количество численных методов, разработанных к настоящему времени, огромно. Одни обладают большей общностью, другие имеют весьма специальное назначение и используются для узкого круга физических задач. Таким образом, начинающие исследователи нуждаются в информации, позволяющей выбрать оптимальный численный метод.

1. Линейные уравнения

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

Запишем в общем виде систему n линейных уравнений для n неизвестных xi, где i = 1, 2,…, n:

Коэффициенты aij и bi (i, j = 1, 2,…, n) являются известными величинами. Первый индекс у коэффициента aij означает номер уравнения в системе, второй индекс ? номер неизвестного, на которое умножается данный коэффициент aij. Коэффициенты bi в правых частях уравнений называются свободными членами. Решить систему (4.1) означает отыскать числа xi (i = 1, 2,…, n), которые при подстановке в (4.1) обращают все уравнения в тождества. Набор этих чисел называется корнями системы (4.1).

Коэффициенты при неизвестных образуют квадратную матрицу A размером n Ч n:

Свободные члены и корни представляются столбцами или nмерными векторами b и x. Тогда систему (4.1) можно записать более кратко в матричном представлении:

A Е x = b

В линейной алгебре доказана следующая теорема: если детерминант (определитель) матрицы A не равен нулю, то система уравнений (4.1) имеет единственное решение. Т.е. при det A ? 0 существует только один набор чисел xi (i = 1, 2,…, n), который обращает в тождество систему (4.1). Следовательно, если мы ищем единственное решение системы уравнений (4.1), то прежде чем ее решать, необходимо убедиться, что детерминант матрицы коэффициентов при неизвестных не равен нулю. (1)

2. Метод Крамера и метод Гаусса

Для решения линейных уравнений применяется метод Крамера и метод Гаусса. Важнейшим недостатком алгоритма Крамера является большое количество необходимых арифметических операций. Для вычисления детерминанта n-го порядка способом разложения по минорам требуется произвести n!Е(n - 1) умножений и примерно столько же делений. Следовательно, при решении системы линейных уравнений 40-го порядка методом Крамера придется выполнить 41Е40!Е39 умножений и сложений. Так как 40! ? 8Е1047, то можно оценить, что при использовании самых быстродействующих компьютеров необходимое время решения во много раз превышает время существования нашей Вселенной. Кроме того, при выполнении процессором большого количества операций накапливается значительная погрешность результата, так как в каждой операции над реальными числами проводится округление. При решении систем линейных уравнений для n = 2 и n = 3 метод Крамера легко реализуется и без использования компьютера. Для больших значений n целесообразно применять более эффективные методы. Метод Гаусса отличается сравнительно малым объемом вычислений и простотой алгоритма, что позволяет легко его программировать. Этот метод заключается, в сущности, в последовательном исключении неизвестных. Процедура вычисления корней системы линейных уравнений состоит из двух частей: прямого хода и обратного хода. Количество арифметических операций при решении системы линейных уравнений в методе Гаусса на порядок меньше, чем в методе Крамера. Это значит, что уже при n ? 4 целесообразно использовать метод Гаусса.

Рассмотрим уравнение вида

f(x) =О,

где f(x) - любая нелинейная или трансцендентная функция, например

f (х) = exp (tg х) - х3 sin х.

Для нахождения корней уравнения (2.40) различают следующие два этапа.

1. Отделение корней, т.е. нахождение таких интервалов по

аргументу х, внутри каждого из которых существует только один корень уравнения (2.40).

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

3. Способы отделения корней

Графический

В графическом способе строится график функции f (х) (рис. 2.2) и приближенно определяются ее нули (или корни уравнения f(x) =О) Заключив эти нули в интервалы , на границах которых выполняются условия и знаки производных первого и второго порядков f'(x), f» (x) на интервалах постоянны, можно утверждать, что внутри каждого из этих интервалов находится один корень уравнения (2.40).

Если при этом то корень двукратный корень (точка 6 на рис. 2.2); если  трехкратный корень (точка ~4 на рис. 2.2) и т.д. В методе половинного деления область определения функции делят на 2, 4, 8, 16, 32,… интервала и для каждого из них анализируют знаки функции на концах интервала; если они противоположны, то внутри интервала находится не менее одного корня; если знак первой производной на интервале постоянный, т.е. (при выполнении предыдущего условия), то внутри интервала находится точно один корень (2)

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

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

Пусть f (х) = О и точное значение корняВ методе половинного деления функция должна удовлетворять следующим двум условиям:

Метод половинного деления состоит в построении последовательности вложенных отрезков  на концах которых удовлетворяются условия (рис. 2.4). Опишем один шаг итерационного метода половинного деления. Пусть на шаге найден отрезок, на котором выполнено условие Этот отрезок делится пополам точкой и вычисляется Если f (xk) = О, то - корень уравнения (2.40). Если, то из двух половин отрезка выбирается та, на концах которой функция имеет противоположные знаки, так как корень находится внутри именно этой половины. Таким образом,  Если необходимо найти корень с точностью е, то деление пополам продолжается до тех пор, пока не выполнится условие (2.42) Тогда значение приближенно определяет корень с точностью (2)

интервал линейный крамер графический

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

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

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

При постановке задачи решения нелинейного уравнения вида f (x) = 0, задается допустимая погрешность е > 0 вычисления корня. Следовательно, в процессе решения ищется не абсолютно точное, а приближенное значение корня. Приемлемым решением называется любое число x, которое удовлетворяет неравенству , где о ? точное значения корня заданного уравнения.

Пусть нам дано уравнение. Находим интервал знакопеременности [a, b], содержащий корень данного уравнения. Алгоритм вычислительного процесса бисекции изображен на рис. 7.2 в форме блок-схемы. Принцип работы алгоритма очевиден из приведенной схемы, поэтому можно ограничиться краткими комментариями. В самом начале задается погрешность вычисления корня е и величина допустимой невязки д. Далее вводятся границы интервала [a, b], содержащего искомый корень, и проверяется свойство знакопеременности функции f(x) на концах заданного интервала. При отсутствии знакопеременности придется изменить границы начального интервала [a, b], в противном случае начинается итерационный процесс. На каждом шаге текущий интервал делится на две равные части точкой с. Эта точка является одной из границ нового, вдвое более узкого, интервала знакопеременности функции f(x). Процесс продолжается до тех пор, пока интервал знакопеременности не станет эже заранее заданной погрешности вычисления корня е. Кроме того, учитывается, что функция f(x) в области своего нуля может иметь очень большую производную. Тогда в найденной точке c?о функция f(x) может иметь значение f(c), значительно отличающееся от нуля. Поэтому в алгоритм добавляется условие, из-за которого уменьшение интервала, содержащего корень, продолжается до тех пор, пока абсолютная величина |f(c)| не станет меньше заранее заданного малого числа д. За приближенное значение искомого корня принимается средняя точка последнего интервала знакопеременности.

Алгоритм схемы половинного деления. a, b - границы интервала, в котором происходит поиск корня, е и д - заданные погрешности для корня и значения функции в точке найденного значения корня, о - значение искомого корня

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

Метод Ньютона

Пусть на интервале [a, b] функция f (x) непрерывна, первая и вторая производные f ?(x) и f ??(x) непрерывны и монотонны. Пусть - некоторое приближенное значение корня из интервала [a, b]. Тогда точное значение корня можно представить в виде (7.4) где - малая поправка. Разложим функцию f (x) в точке в ряд Тейлора по степеням малой величины до линейного члена

Так как то величина поправки выразится из уравнения (7.5) таким образом:

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

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

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

На рис. 7.3.а изображен случай, когда вторая производная f ??(x) > 0 на всем интервале [a, b], f (a) < 0, f (b) > 0. Примем за начальное приближение корня x0 = a. Величина производной f ?(x0) равна тангенсу угла наклона касательной к графику функции f(x0) в точке x0. Следовательно, первая поправка к корню (7.6) на рис. 7.3.а изобразится отрезком ad. Точка d (следующее приближение корня x1) лежит вне интервала [a, b]. Следовательно, дальнейшее использование итераций по формуле (7.7) некорректно. Если за начальное приближение корня принять x0 = b, то первый шаг процесса (7.7) даст следующее приближение корня x1 = с, которое лежит внутри интервала [a, b]. При этом видно, что дальнейшие приближения x2, x3, x4 … будут располагаться слева от истинного значения корня о. Последовательность приближений xn сходится к о справа налево вдоль числовой оси x.

На рис. 7.3.б приведен другой случай, когда на всем интервале [a, b] вторая производная f ??(x) < 0. Аналогичные рассуждения вновь показывают справедливость условия сходимости (7.8). В данном случае последовательность приближений xn (n = 1, 2, …) сходится к истинному значению корня о слева направо. После выбора начального приближения корня запускается процесс (7.7) и останавливается по достижении требуемой погрешности. Ясно, что для использования метода Ньютона необходимо, чтобы производная f ?(x) нигде на интервале поиска корня не равнялась нулю. Свойства рекуррентного соотношения таковы, что в общем случае условие |xn ? xn?1|<е не обеспечивает выполнения неравенства |xn ?о|<е. В курсе численных методов получено следующее соотношение для оценки погрешности достигнутого приближения искомого корня xn:

где M2 - максимум абсолютной величины второй производной f ??(x) на интервале [a, b]:

m1 - минимум абсолютной величины первой производной f ?(x) на том же интервале

(1)

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

Этот метод весьма сходен с методом Ньютона, но на каждом шаге итераций вместо производной используется разделенная разность

Подстановка выражения (7.13) вместо производной в уравнение (7.7) дает рекуррентное соотношение для поиска корня уравнения (7.1) в следующем виде:

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

Для сходимости процесса (7.14) требуется лишь непрерывность функции f (x). Справедливости ради следует заметить, что при выделении интервала, содержащего единственный корень, ранее нам пришлось использовать монотонность первой производной f ?(x). Кроме того, ясно, что если на каком-либо шаге процесса (7.14) окажется f (xn) = f (xn?1), то произойдет сбой алгоритма.

Условия сходимости, как правило, обеспечиваются на первом этапе решения уравнения (7.1) при выборе интервала знакопеременности функции f (x). При постоянстве знака второй производной f ??(x) на интервале поиска корня процесс (7.14) сходится почти так же быстро, как и процесс Ньютона (7.7). Для оценки погрешности достигнутого приближения корня можно воспользоваться очевидным неравенством:

где величина m1 определена формулой (7.11). В курсе вычислительной математики доказано, что при использовании метода секущих выполнение условия гарантирует неравенство т.е. достижение заданной погрешности вычисления искомого корня о. Скорость сходимости метода секущих, вообще говоря, несколько ниже, чем у метода Ньютона, что искупается гораздо более общими условиями сходимости. Это значит, что количество шагов процесса (7.14) может быть несколько больше, чем у процесса (7.7). Но при использовании рекуррентной формулы (7.14) не приходится многократно вычислять значения первой производной f ?(x) на каждом шаге итерации и, можно вообще не рассматривать поведение второй производной f ??(x) на интервале [a, b]. (1)

4. Теорема Штурма

Рассмотрим пример отделения корней многочлена по методу Штурма на примере многочлена .

Для применения этого метода к многочлену требуется составить систему Штурма .

Замечание: многочлен должен иметь действительные коэффициенты и не иметь кратных корней.

Правило построение системы Штурма:

1)

2) Если известны и , то будет равен остатку от деления на , взятым с обратным знаком:

.

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

Составим систему Штурма для заданного многочлена

1)

2)

Умножаем остаток на 4 и берем его с противоположным знаком.

Получим

3)

Домножим на 25, поменяем знак и получим:

4)

Домножим остаток на обратную величину, поменяем знак и получим:

Получили систему Штурма:

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

И т.д. Занесем результаты выводов в таблицу:

Вывод: Многочлен имеет ровно действительных корня.

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

Замечание: повезло, т.к. при получаем , т.е. - корень многочлена. Мы не только локализовали, но определили его точное значение. Заметим, что количество перемен знаков уменьшается на 2, т.е. на этом интервале есть один корень, он дает одно изменение, и корень в этой точке дает еще одну перемену. Но продолжим.

Вывод: про корни можно сказать:

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

интервал линейный крамер графический

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

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

1. Фаддеев М.А., Марков К.А. ЧИСЛЕННЫЕ МЕТОДЫ (Учебное пособие). б.м.: НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ.Н.И.ЛОБАЧЕВСКОГО, ННГУ, 2010.

2. Д.Л. Ревизников, В.Ф. Формалев. ЧИСЛЕННЬIЕ МЕТОДЬI. Москва: МОСКВА Физмдтлит® 2006, 2006.

3. http://kontromat.ru/.

4. А., Самарский А. ВВЕДЕНИЕ В ЧИСЛЕННЫЕ МЕТОДЫ. Москва: наука, 1982.

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