Решение нелинейных уравнений методом Ньютона

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

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

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

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

Математика как наука возникла в связи с необходимостью решения практических задач: измерений на местности, навигации и т.д. Вследствие этого математика была численной математикой и ее целью было получение решения в виде числа. Численное решение прикладных задач всегда интересовало математиков. Крупнейшие представители прошлого сочетали в своих исследованиях изучение явлений природы, получение их математического описания, т.е. его математической модели и его исследование. Анализ усложненных моделей потребовал создания специальных, обычно численных методов решения задач. Названия некоторых таких методов свидетельствуют о том, что их разработкой занимались крупнейшие ученые своего времени. Это методы Ньютона, Эйлера, Лобачевского, Гаусса, Чебышева, Эрмита.

Настоящее время характерно резким расширением приложений математики, во многом связанным с созданием и развитием средств вычислительной техники. В результате появления ЭВМ менее чем за 40 лет скорость выполнения операций возросла от 0,1 операции в секунду при ручном счете до 10 операций в секунду на современных ЭВМ.

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

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

во-первых, только применение математических методов позволяет придать количественный характер исследованию того или иного явления материального мира;

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

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

Математические модели.

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

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

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

Основные требования, предъявляемые к математической модели - адекватность рассматриваемому явлению, т.е. оно должно достаточно отражать характерные черты явления. Вместе с тем она должна обладать сравнительной простотой и доступностью исследования.

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

Математические модели можно классифицировать по разным признакам: статические и динамические, сосредоточенные и распределенные; детерминированные и вероятностные.

Рассмотрим задачу нахождения корней нелинейного уравнения

f(x)=0 (1)

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

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

Существование на найденном отрезке [a,b], по крайней мере, одного корня уравнения (1) следует из условия Больцано:

f(a)*f(b)<0 (2)

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

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

, (3)

где вещественные коэффициенты.

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

б) Число положительных вещественных корней меньше или равно числа переменных знаков в последовательности коэффициентов . Замена х на -х в уравнении (3) позволяет таким же способом оценить число отрицательных корней.

На втором этапе решения уравнения (1), используя полученное начальное приближение, строится итерационный процесс, позволяющий уточнять значение корня с некоторой, наперед заданной точностью . Итерационный процесс состоит в последовательном уточнении начального приближения. Каждый такой шаг называется итерацией. В результате процесса итерации находится последовательность приближенных значений корней уравнения . Если эта последовательность с ростом n приближается к истинному значению корня x , то итерационный процесс сходится. Говорят, что итерационный процесс сходится, по меньшей мере, с порядком m, если выполнено условие:

, (4)

где С>0 некоторая константа. Если m=1 , то говорят о сходимости первого порядка; m=2 - о квадратичной, m=3 - о кубической сходимостях.

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

; (5,6)

или малости невязки:

(7)

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

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

1)Метод итераций. При решении нелинейного уравнения методом итераций воспользуемся записью уравнения в виде x=f(x). Задаются начальное значение аргумента x₀ и точность е. Первое приближение решения x₁ находим из выражения x₁=f(x₀), второе - x₂=f(x₁) и т.д. В общем случае i+1 приближение найдем по формуле xi+1 =f(xi). Указанную процедуру повторяем пока |f(xi)|>е. Условие сходимости метода итераций |f'(x)|<1.

2)Метод Ньютона. При решении нелинейного уравнения методом Ньтона задаются начальное значение аргумента x₀ и точность е. Затем в точке(x₀,F(x₀)) проводим касательную к графику F(x) и определяем точку пересечения касательной с осью абсцисс x₁. В точке (x₁,F(x₁)) снова строим касательную, находим следующее приближение искомого решения x₂ и т.д. Указанную процедуру повторяем пока |F(xi)| > е. Для определения точки пересечения (i+1) касательной с осью абсцисс воспользуемся следующей формулой

x_i+1=x_i-F(x_i)\ F'(x_i).

Условие сходимости метода касательных F(x₀)•F''(x)>0, и др.

3). Метод дихотомии. Методика решения сводится к постепенному делению начального интервала неопределённости пополам по формуле

С_к=а_к+в_к/2.

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

Процесс деления отрезка проводится до тех пор, пока длина текущего интервала неопределённости не будет меньше заданной точности, то есть в_{к -} а_к < E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости.

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

c = a - (f(a)Ч (a-b)) / (f(a) - f(b)),

c = b - (f(b)Ч (a-b)) / (f(a) - f(b)).

Следующее приближение ищется на интервале [a,c] или [c,b] в зависимости от знаков значений функции в точках a,b,c

x* О [c,b] , если f(с)Ч f(а) > 0 ;

x* О [a,c] , если f(c)Ч f(b) < 0 .

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

x₀=a, x_i+1 = x_i - f(x_i)(b-x_i) / (f(b)-f(x_i), при f '(x)Ч f "(x) > 0 ;

x₀=b, x_i+1 = x_i - f(x_i)(x_i-a) / (f(x_i)-f(a), при f '(x)Ч f "(x) < 0 .

Сходимость метода хорд линейная

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

Наиболее общий вид нелинейного уравнения:

f(x) =0 (2.1)

где функция f(x) определена и непрерывна на конечном или бесконечном интервале [а, b].

Определение 2.1. Всякое число , обращающее функцию f(x) в нуль, называется корнем уравнения (2.1).

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

(2.2)

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

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

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

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

(2.3)

где -- действительные коэффициенты уравнения, х -- неизвестное.

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

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

Решить уравнение (2.1) означает:

1. Установить имеет ли уравнение корни.

2. Определить число корней уравнения.

3. Найти значения корней уравнения с заданной точностью.

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

Алгоритм нахождения корня уравнения с помощью численного метода состоит из двух этапов:

1) отделение или локализация корня, т.е. установление промежутка [a,b], в котором содержится один корень:

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

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

Теорема 2.1. Если функция у = f(х) непрерывна на отрезке [а,b] и f(а)=А, f(b)=В, то для любой точки С, лежащей между А и В, существует точка , что .

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

Пусть область определения и непрерывности функции является конечным отрезком [а,b]. Разделим отрезок на n частей: ,

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

(2.4)

т.е. , или , . Эти отрезки и содержит хотя бы по одному корню.

Теорема 2.2. Если функция у = f(х) непрерывна на отрезке [а;b ], f(а)f(b)<0 и f`(х) на интервале (а;b) сохраняет знак, то внутри отрезка [а;b] существует единственный корень уравнения f(х) = 0.

Для отделения корней можно использовать также график функции у = f(х). Корнями уравнения (2.1) являются те значения х, при которых график функции y=f(х) пересекает ось абсцисс. Построение графика функции даже с малой точностью обычно дает представление о расположении корней уравнения (2.1). Если построение графика функции у=f(x) вызывает затруднение, то исходное уравнение (2.1) следует преобразовать к виду ц1(х) = ц2(х) таким образом, чтобы графики функций у = ц1(х) и у = ц2(х) были достаточно просты. Абсциссы точек пересечения этих графиков и будут корнями уравнения (2.1).

Пример 1. Отделить корни уравнения x²-2cosx=0.

Решение. Рассмотрим два способа отделения корней.

а) Графический способ. Перепишем уравнение в виде x²=2cosx и построим график функций y=x² и y=2cosx в одной и той же системе координат (рисунок 5). так как эти графики пересекаются в двух точках, уравнение имеет два корня, расположенные симметрично относительно начала координат на интервалах (-/2; 0) и (0; /2).

б) Аналитический способ. Пусть f(x)=x²-2cosx. Так как f(x) четная функция, то достаточно рассмотреть только неотрицательные значения x. В силу неравенства 2cosx2<(/2)², положительные корни уравнения, если они существуют, будут меньше /2.

Производная f'(x)=2(x+sinx). На интервале (0; /2) f'(x)>0 , следовательно, f(x) здесь монотонно возрастает и ее график может пересечь ось х не более, чем в одной точке. Заметим, что f(0)=-2<0, а f(/2)=(/2)²>0. Значит, уравнение имеет один положительный корень, лежащий на интервале (0; /2). В силу четности функции уравнение имеет также один отрицательный корень, симметричный положительному. Теперь перейдем к уточнению корня. Для применения комбинированного метода уточнения корня необходимо убедится, что f ''(x) на (0; /2) сохраняет знак, и выбрать начальное приближение корня для применения метода касательных. Оно должно удовлетворять условию: f(x)f ''(x)>0. Так как f ''(x)=2(1+cosx) положительна на [0; /2], то за начальное приближение корня в методе касательных может быть взято /2. Следовательно, можно положить x=/21,570796, x₁=0 (см схему алгоритма). В нашем случае метод хорд будет давать приближенное значение корня с недостатком, а метод касательных - с избытком.

Рассмотрим один итерационный шаг уточнения корня. Вычислим значения f(0), f(/2), f'(/2). Новые значения x₁ и x найдем соответственно по формулам:

|x-x₁|=0,387680,4>10^-4=.

Заданная точность не достигнута, и вычисления нужно продолжить.

Следовательно, приближенное значение корня с нужной точностью найдено в результате трех итераций и приближенно равно 1,0217.

В силу симметрии графика функции f(x) значение второго корня приближенно равно -1,0217.

Уточнение корня.

Постановка задачи. Допустим, что искомый корень уравнения (2.1) отделен, т.е. найден отрезок [а ; b], на котором имеется один и только один корень уравнения. Любую точку этого отрезка можно принять за приближенное значение корня. Погрешность такого приближения не превосходит длины [а ; b]. Следовательно, задача отыскания приближенного значения корня с заданной точностью сводится к нахождению отрезка [а ; b] (b-a < ), содержащего только один корень уравнения (2.1). Эту задачу обычно называют задачей уточнения корня.

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

В этой связи задача нахождения корней многочлена вида (3.1)

(3.1)

представляет особый интерес, т.к. формулы нахождения корней даже кубического уравнения достаточно сложны. Если необходимо отыскать корни многочлена, степень которого равна, например, 5 - то без помощи численных методов не обойтись, тем более, что вероятность наличия у такого многочлена натуральных (или целых, или точных корней с «короткой» дробной частью) довольно мала, а формул для нахождения корней уравнения степени, превышающей 4, не существует. Де-факто все дальнейшие операции будут сводиться лишь к уточнению корней, интервалы которых приблизительно известны заранее. Проще всего эти «приблизительные» корни находить, используя графические методы.

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

Метод бисекций (известный еще и как «метод деления отрезка пополам») также является рекурсивным, т.е. предусматривает повторение с учетом полученных результатов.

Суть метода половинного деления заключается в следующем:

- дана функция F(x);

- определена допустимая погрешность Q;

- определен некоторый интервал [ a , b ], точно содержащий решение уравнения.

1) Вычисляем значение координаты Е, беря середину отрезка [a , b], т.е.

Е= (a + b ) / 2 (3.2)

2) Вычисляем значения F(a), F(b), F(E), и осуществляем следующую проверку: Если F(E)>Q, то корень с указанной точностью найден. Если F(E)<Q, т.е. необходимая точность еще не достигнута, то формируем два интервала: [a , E] и [E , b] роверяяем знаки F(a), F(b), F(E). На концах одного из этих интервалов знаки функции будут одинаковы, а на друго различны (иначе Е - искомый корень). И именно то интервал, на концах которого знаки различны, мы берем за основу при следующей итерации, т.е. приравниваем к Е либо a, либо b.

3) Переходим к пункту 1.

Метод простых итераций (метод последовательных приближений). Заменим уравнение (2.1) эквивалентным ему уравнением

x=(x) (3.3)

можно сделать различными способами, например

х=х+сf(x), c0. (3.4)

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

х _n+1=(x_n), n=0,1,2,… (3.5)

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

Если на отрезке [a,b], содержащем х₀ и все последующие приближения х_n, nN, функция (x) имеет непрерывную производную '(x) и |'(x)|q<1, то итерационная последовательность (3.5) сходится к единственному на [a,b] корню уравнения (3.3). Скорость сходимости определяется неравенством

.

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

Следовательно, на практике при нахождении корней методом простой итерации желательно представить уравнение (2.1) в форме (3.3) таким образом, чтобы производная '(x) в окрестности корня по абсолютной величине была, возможно, меньше. Для этого иногда пользуются параметром с из формулы (3.4).

Метод Ньютона (метод касательных). Если известно достаточно хорошее начальное приближение , для которого выполняется неравенство:

,

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

,

В качестве начального приближения можно использовать границы интервала , причем:

если на ,

, если на .

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

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

,

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

Правило останова:

, где .

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

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

Рассмотрим следующий случай:

- дана функция F(x) и построен ее график;

- определена допустимая погрешность Q

- на основании графика определен отрезок [a,b], на котором график функции пересекает ось абсцисс, следовательно, на этом отрезке существует корень рассматриваемого многочлена (обозначим его через A)

Дальнейший алгоритм сводится к следующим действиям:

1) строим касательную к графику функции в точке F(b)

2) вычисляем координату х пересечения касательной с осью абсцисс по формуле (3.9) и обозначаем ее через b'

3) строим к графику функции хорду, проходящую через точки F(a) и F(b).

4) Вычисляем точку пересечения хорды с осью абсцисс по формуле (2) и обозначаем ее через a'.

(3.6)

(3.7)

Таким образом мы получаем новый отрезок [a' , b'], который (по определениям хорды и касательной) по прежнему содержит решение уравнения A.

Теперь принимаем отрезок [a',b'] за новый отрезок [a,b] и повторяем шаги 1-4 до тех пор, пока разность F(b)-F(a) не станет меньше первоначально заложенной погрешности Q. Отметим также, что после этого рекомендуется в качестве искомого решения взять среднее арифметическое F(a) и F(b).

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

Замечание к методу хорд и касательных. Так как для решения поставленной задачи требуется отыскание производной функции F(x), метод хорд и касательных достаточно трудно реализуем на программном уровне, т.к. правила вычисления производных в общем виде довольно громоздки для «понимания» ЭВМ; при непосредственном указании производной для каждой степени многочлена память компьютера серьезно загружается, что очень замедляет работу, а задание функции и, соответственно, ее производной непосредственно в программном коде - недопустимо. Однако, используя данный метод, сходимость интервала к корню происходит наиболее быстро, особенно если совместить метод хорд и касательных с методом бисекции, т.к. середина нового отрезка зачастую дает вполне удовлетворительное решение.

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

,

. (3.8)

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

,

Алгоритм метода секущих:

1) заданы начальное значение и погрешность . Вычислим

;

2) для n = 1,2, ….. пока выполняется условие , вычисляем по формуле (3.8):

1.2 Алгоритм метода Ньютона

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

.

Далее получим следующее приближение в точке , проводя касательную из точки () до пересечения с осью абсцисс:

(8)

Продолжая этот процесс, получим известную формулу Ньютона:

(9)

y

Приведем простейшую рекурсивную подпрограмму-функцию:

function X_Newt(x,eps:real):real;

var y:real;

begin

y:=x-f(x)/f1(x);

if abs(f(x)) > eps

then X_Newt:=X_Newt(y,eps)

else X_Newt:=y

end;

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

Преобразуем уравнение (1) к эквивалентному уравнению вида:

x=g(x) (10)

В случае метода касательных

.

Если известно начальное приближение к корню x=x₀, то следующее приближение найдем из уравнения x₁=g(x₀), далее x₂=g(x₁),... Продолжая этот процесс, получим рекуррентную формулу метода простой итерации

x_k+1=g(x_k) (11)

Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (5-7).

Всегда ли описанный вычислительный процесс приводит к искомому решению? При каких условиях он будет сходящимся? Для ответа на эти вопросы опять обратимся к геометрической иллюстрации метода.

Корень уравнения представляется точкой пересечения функций y=x и y=g(x). Как видно из рис. 3(а), если выполняется условие , то процесс сходится, иначе - расходится.

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

(12)

Переход от уравнения f(x)=0 к уравнению х=g(x) можно осуществлять различными способами. При этом важно, чтобы выбранная функция g(x) удовлетворяла условию (12). К примеру, если функцию f(x) умножить на произвольную константу q и добавить к обеим частям уравнения (1) переменную х, то g(x)=q*f(x)+x . Выберем константу q такой, чтобы скорость сходимости алгоритма была самой высокой. Если 1<g'(x)<0, то сходимость итерационного процесса будет двусторонней. Производная по х от этой функции: g'(x)=1+q*f'(x). Наибольшую сходимость получим при g'(x)=0, тогда q= - 1/f'(x) и формула (11) переходит в формулу Ньютона (9).

Метод Ньютона обладает высокой скоростью сходимости, однако он не всегда сходится. Условие сходимости , где g(x) = x - f(x)/ f'(x), сводится к требованию

.

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

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

(13)

Другой метод модификации - замена производной конечной разностью

(14)

(15)

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

Запишем в общем виде алгоритм метода Ньютона.

1. Задать начальное приближение х⁽⁰⁾ так, чтобы выполнилось условие

f(x⁽⁰⁾)*f''(x⁽⁰⁾)>0. (16)

Задать малое положительное число е , как точность вычислений. Положить к = 0.

2. Вычислить х^(к+1) по формуле (9) :

.

3. Если | x^(k+1) - x^(k) | < е, то процесс вычисления прекратить и положить х* = x^(k+1). Иначе увеличить к на 1 (к = к + 1) и перейти к пункту 2.

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

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

Многие прикладные задачи радиофизики и электроники требуют решения систем нелинейных алгебраических уравнений (СНАУ)

или в векторной форме

,(2.1)

где - вектор-столбец переменных, - вектор-столбец функций, - n-мерное векторное пространство.

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

Различают одношаговые и многошаговые итерационные методы. В m-шаговом итерационном методе при построении приближения используются приближения на m предыдущих шагах. Общую схему наиболее распространенных на практике так называемых неявных одношаговых методов можно представить в виде

,

при этом - [nxn]-неособенная матрица, задающая итерационный процесс, - числовой параметр. Построение (k+1)-го приближения в этой схеме осуществляется посредством решения линейной системы

,(2.2)

где .

Если для всех , здесь- [nxn]-единичная матрица, то итерационный метод называют явным, так как в этом случае Метод является стационарным, когда и не зависят от номера итерации, и нестационарным в противном случае.

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

,

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

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

Предположим, что известно k-е приближение к точному решению системы (2.1). Следующее (k+1)-е приближение в методе Ньютона вычисляется как

, (2.3)

при этом вектор поправки находится путем решения системы линейных алгебраических уравнений

,(2.4)

где - [nxn]-матрица Якоби, определяемая следующим образом:

.

Из сравнения соотношений (2.2) и (2.4) следует, что метод Ньютона является одношаговым, неявным, нестационарным итерационным правилом.

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

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

и ,(2.5)

где ,

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

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

Используя метод простой итерации, найти наименьший положительный корень уравнения е^хsinx-1=0 (=10^-4).

Решение. Запишем уравнение в виде:x=x+c(е^хsinx-1), то есть в нашем случае (x)=x+c(е^хsinx-1).

Выберем постоянную величину с так, чтобы |'(x)|=|1+ce^x(sinx+cosx)|<1 на [0;/2]. Очевидно, что при с>0 этого достичь нельзя.

На интервале (0; /2) при c<0 ''(x)=2ce^xcosx - величина отрицательная, а значит '(x) на этом интервале монотонно убывает. Поэтому наибольшее значение '(x) при любом фиксированном отрицательном значении с будет достигаться при x=0, '(0)=1+c а наименьшее при x=/2, '(/2)1+4,8c.

Приравнивая эти выражения нулю, получим два значения для с: с=-1, с-0,21. Следовательно, если бы искомый корень был близок к нулю, то в качестве с можно было бы взять число, близкое к-1; если бы корень был близок к /2, то в качестве с можно было бы взять число близкое к-0,2. Но, так как положение корня на неизвестно, возьмем с=(-1-0,2)/2=-0,6, т.е. выберем среднее арифметическое полученных ранее значений.

За начальное приближение х₀ искомого значения корня возьмем примерную середину отрезка, например х₀=0,7.

Результаты вычислений по формулам x_n+1 = x_n-0,6(e^x_nsinx_n-1), nN, выполненные на МК, приведены в таблице 5. промежуточные вычисления проводились с двумя запасными знаками. Последний столбец таблицы состоит из левых частей неравенства, округленных до двух значащих цифр.

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

Варианты заданий:

Описание алгоритма

Алгоритм решения систем нелинейных алгебраических уравнений методом Ньютона реализуется следующим образом:

Алгоритм 2.1

Ввести начальное приближение , параметры и , предельное число итераций и положить .

Вывести на экран шапку таблицы, содержащей информацию о сходимости метода: номер итерации, и .

Вычислить вектор невязки:

.

Вычислить матрицу Якоби:

.

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

.

Уточнить решение:

.

Вычислить по формулам (2.5) и вывести на экран текущие значения и текущий номер итерации.

Проверить критерий (2.5) завершения итерационного процесса. Если этот критерий выполняется, то выйти из программы.

Проверить условие . Если это условие имеет место, то выйти из итерационного процесса с сообщением .

10. Положить и перейти к п. 3.

Пример 1

Решить уравнение методом Ньютона.

sin x² + cos x² - 10x. = 0.

Вычисления производить с точностью е = 0, 001.

Решение: Вычислим первую производную функции.

F'(x)=2x cos x² - 2x sin x² - 10.

Теперь вычислим вторую производную от функции.

F''(x)=2cos x² - 4 x²sin x² - 2sin x² - 4 x²cos x² = cos x² (2-4 x² ) - sin x² (2+4x²).

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 0, 565, тогда f(0. 565)*f''(0. 565) = -4. 387 * (-0. 342) = 1. 5 > 0,

Условие выполняется, значит, берём x⁽⁰⁾ = 0, 565.

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

Отсюда следует, что корень уравнения х = 0, 101.

Пример 2

Решить уравнение методом Ньютона.

cos x - e^-x2/2 + x - 1 = 0

Вычисления производить с точностью е = 0, 001.

Решение: Вычислим первую производную функции.

F'(x) = 1 - sin x + x*e^-x2/2.

Теперь вычислим вторую производную от функции.

F''(x) = e^-x2/2 *(1-x²) - cos x.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 2, тогда f(2)*f''(2) = 0. 449 * 0. 010 = 0.05 > 0,

Условие выполняется, значит, берём x⁽⁰⁾ = 2.

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

Отсюда следует, что корень уравнения х = 1. 089.

Пример 3

Решить уравнение методом Ньютона.

x² - e^-x = 0.

Вычисления производить с точностью е = 0, 001.

Решение: Вычислим первую производную функции.

F'(x) = 2*x + e^-x.

Теперь вычислим вторую производную от функции.

F''(x) = 2 - e^-x.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f''(2) = 0. 632 * 1, 632 = 1, 031 > 0,

Условие выполняется, значит берём x⁽⁰⁾ = 1.

Отсюда следует, что корень уравнения х = 0, 703.

Пример 4.

Решить уравнение методом Ньютона.

cos x -e^-x/2+x-1=0.

Решение: Вычислим первую производную функции.

F'(x) = -sin x + e^-x/2/2+1.

Теперь вычислим вторую производную от функции.

F''(x) = -cos x - e^-x/2 /4.

Построим приближённый график данной функции.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f''(2) = -0. 066 * (-0. 692) = 0. 046 > 0,

Условие выполняется, значит, берём x⁽⁰⁾ = 1.

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

Отсюда следует, что корень уравнения х = 1. 162.

Пример 5

Решить уравнение методом Ньютона.

-2+e^x- e^-x =0.

Решение: Вычислим первую производную функции.

F'(x) = e^x+e^-x.

Теперь вычислим вторую производную от функции.

F''(x) = e^x-e^-x.

Теперь, исходя из графика, возьмём первый приближённый корень и проверим условие (16) : f(x⁽⁰⁾) * f''(x⁽⁰⁾) > 0.

Пусть x⁽⁰⁾ = 1, тогда f(2)*f''(2) = 0. 350 * 2, 350 = 0. 823 > 0,

Условие выполняется, значит, берём x⁽⁰⁾ = 1.

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

Отсюда следует, что корень уравнения х = 0, 881.

Решение нелинейного уравнения аналитически

Определим корни уравнения х³ + 0,1х² + 0,4х - 1,2 = 0 аналитически. Находим:

f (x) = х³ + 0,1х² + 0,4х - 1,2

f ` (x) = 3х² + 0,1х + 0,4

f (-1) = - 2,5 < 0f (0) = - 1,2 < 0f (+1) = 0,3 > 0

Следовательно, уравнение имеет действительный корень, лежащий в промежутке [0; +1].

max |f ' (x) | = f ' (+1) = 3 + 0,1 + 0,4 = 3,5 R = 2.

Тогда

(x) = x - (f (x) / R) = x - 0,5 х³ - 0,05 х² - 0,2 х + 0,6 = - 0,5 х³ - 0,05 х² + 0,8 х + 0,6.

Пусть х₀ = 0, тогда х _n+1 = (х _n).

2. Блок схема программы

3. Разработка программного продукта

Описание программы

В программе используется глобальная переменная Form1, которая представляет собой экранную форму.

Для организации интерфейса с пользователем были разработаны экранные формы, в результате чего на экранной форме Form1 поместили элементы, приведенные в таблице 3.1

Таблица 3.1Описание визуальных объектов на форме Form1

Таблица 3.2 Переменные программы

Для хранения данных о компьютере разработаем составной тип данных TComp c полями, приведенными в таблице 3.3

Таблица 3.3 Информационные поля

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

Таблица 3.4 Пользовательские процедуры и обработчики событий

Более подробно некоторые процедуры будут рассмотрены далее.

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

Описание пользовательских процедур

Функция GetComp предназначена для поиска компьютера в массиве по имени. Синтаксис:

GetComp(name:string;AComp:ATComp;var Comp:TComp):boolean.

Где name - наименование компьютера, AComp - массив в котором производится поиск, Comp - объект, в который возвращается найденный объект.

Если поиск удачен, то функция возвращает значение true, иначе - false.

Процедура ShowComp предназначена для вывода информации о компьютере в поля формы. Синтаксис:

ShowComp(Comp:TComp).

Где Comp - запись, хранящая информацию о компьютере.

Процедура ShowCompInGrid предназначена для вывода информации о компьютере в поля таблицы. Синтаксис:

ShowCompInGrid(Comp:TComp; Sgr:TStringGrid;Row:integer),

где Comp - запись, хранящая информацию о компьютере,

SGr - таблица, в которую производится вывод,

Row - номер строки, в которую выводится информация.

Процедура ShowAComp предназначена для вывода информации о всех компьютерах из массива AComp в поля таблицы. Синтаксис:

ShowAComp(AComp:ATComp;Sgr:TStringGrid).

где AComp - массив записей, хранящий информацию о компьютерах,

SGr - таблица, в которую производится вывод.

Описание процедуры BOpenClick