Приближённые методы решения алгебраического уравненияОднако в число алгебраических уравнений можно также включить те уравнения, которое после некоторых преобразований, можно привести к алгебраическому. Те методы, которые здесь рассматриваются, применимы, как к алгебраическим уравнениям, так и к трансцендентным . Корнем уравнения (1 .1 ) называется такое число x , где f ( x )=0. При определении приближённых корней уравнения (1 .1 ) необходимо решить две задачи: 1) отделение корней, т. е. определение достаточно малых промежутков, в каждом из которых заключён один и только один корень уравнения (простой и кратный); 2) уточнение корней с заданной точностью (верным числом знаков до или после запятой); Первую задачу можно решить, разбив данный промежуток на достаточно большое количество промежутков, где бы уравнение имело ровно один корень: на концах промежутков имело значения разных знаков. Там где данное условие не выполняется, те промежутки откинуть. Вторая задача решается непосредственно в методах рассмотренных ниже. При графическом отделении корней уравнения (1 .1 ) нужно последнее преобразовать к виду: j 1 ( x )= j 2 ( x ) (2 .1 ) и построить графики функций y 1 = j 1 ( x ), y 2 = j 2 ( x ). Действительно, корнями уравнения (1 .1 ) f ( x ) = j 1 (x) - j 2 (x) = 0 являются абсциссы точек пересечения этих графиков (и только они). Из всех способов, какими можно уравнение (1 .1 ) преобразовать к виду (2.1) выбираем тот, который обеспечивает наиболее простое построение графиков y 1 = j 1 ( x ) и y 2 = j 2 ( x ). В частности можно взять j 2 ( x ) = 0 и тогда придём к построению графика функции (1 .1 ), точки пересечения которого с прямой y 2 = j 2 ( x )=0, т. е. с осью абсцисс, и есть искомые корни уравнения (1 .0 ). Условия, наложенные на функцию f ( x ) на отрезке [ a , b ]. Будем предполагать, что функция f ( x ) непрерывна на отрезке [ a , b ] (для метода хорд можно потребовать на интервале) и имеет на этом интервале первую и вторую производные, причём обе они знакопостоянны (в частности отличны от нуля). Будем также предполагать, что функция f ( x ) принимает на концах отрезка значения разного знака. В силу знакопостоянства первой производной функция f ( x ) строго монотонна, поэтому при сделанных предположениях уравнение (1 .1 ) имеет в точности один корень на интервале ( a , b ). 2. Метод дихотомии Этот метод ещё называется методом вилки. Нам необходимо найти корень уравнения (1.1) на отрезке [ a , b ]. Рассмотрим отрезок [ x 0 , x 1 ]: [ x 0 , x 1 ] [ a , b ]. Пусть мы нашли такие точки х 0 , х 1 , что f (х 0 ) f (х 1 ) 0, т. е. на отрезке [х 0 , х 1 ] лежит не менее одного корня уравнения. Найдём середину отрезка х 2 =(х 0 +х 1 )/2 и вычислим f (х 2 ). Из двух половин отрезка выберем ту, для которой выполняется условие f (х 2 ) f (х гран .) 0, так как один из корней лежит на этой половине. Затем новый отрезок делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис 1.2). Дихотомия проста и очень надёжна. К простому корню она сходится для любых непрерывных функций в том числе и не дифференцируемых; при этом она устойчива к ошибкам округления. Скорость сходимости не велика; за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трёх цифр требует 10 итераций. Зато точность ответа гарантируется. рис. 1.2 Приступим к доказательству того, что если непрерывная функция принимает на концах некоторого отрезка [ a , b ] значения разных знаков, то методом дихотомии однозначно будет найден корень. Предположим для определённости, что функция f ( x ) принимает на левом конце отрезка [ a , b ] отрицательное значение, а на правом – положительное: f (a) f(b) > 0. Возьмём среднюю точку отрезка [ a , b ] , h =( a + b )/2 и вычислим значение в ней функции f ( x ). Если f ( h )=0, то утверждение теоремы доказано: мы нашли такую точку, где функция обращается в нуль. Если f ( h ) ¹ 0, тогда из отрезков [ a , h ] и [ h , b ] выберем один из них тот, где функция на его концах принимает значения разных знаков. Обозначим его [ a 1 , b 1 ]. По построению: f ( a 1 ) f ( b 1 )>0. Затем среднюю точку отрезка [ a 1 , b 1 ] точку h 1 и проведём тот же алгоритм нахождения другого отрезка [ a 2 , b 2 ] где бы по построению f ( a 2 ) f ( b 2 )>0. Будем продолжать этот процесс. В результате он либо оборвётся на некотором шаге n в силу того, что f ( h n )=0, либо будет продолжаться неограниченно. В первом случае вопрос о существовании корня уравнения f ( x )=0 решён, поэтому рассмотрим второй случай. Неограниченное продолжение процесса даёт последовательность отрезков [ a , b ], [ a 1 , b 1 ], [ a 2 , b 2 ],… Эти отрезки вложены друг в друга – каждый последующий отрезок принадлежит всем предыдущим: a n a n+ 1 n+ 1 b n (1.2) причём : f (a n ) f(b n ) > 0 Длины отрезков с возрастанием номера n стремятся к нулю: Согласно (1.2) они образуют монотонно убывающую ограниченную последовательность { a n }. Такая последовательность имеет предел, который можно обозначить через c 1 : Обозначим его через с 2 : Процесс построения последовательности вложенных стягивающих отрезков методом вилки (дихотомии) является эффективным вычислительным алгоритмом решения уравнения f ( x )=0. На n -ом шаге процесса получаем: a n c b n Это двойное неравенство показывает, что число a n определяет корень с недостатком, а число b n с избытком, с ошибкой не превышающей длину отрезка D n=b n -a n =(b-a)/2n. При увеличении n ошибка стремится к нулю по закону геометрической прогрессии со знаменателем q=0.5. Если задана требуемая точность e >0, то чтобы её достигнуть достаточно сделать число шагов N, не превышающее log 2 [(b-a)/ e ]: N>log 2 [(b-a)/ e ]. 3. Метод итераций Этот метод называется ещё методом последовательных приближений. Пусть нам необходимо найти корень уравнения (1.1) на некотором отрезке [ a , b ]. Предположим, что уравнение (1.0) можно переписать в виде: x = j ( x ) (1.3) Возьмём произвольное значение x 0 из области определения функции j ( x ) и будет строить последовательность чисел { x n }, определённых с помощью рекуррентной формулы: x n +1 = j (x n ), n=0, 1, 2, … (2.3) Последовательность { x n }называется итерационной последовательностью. При её изучении встают два вопроса: 1) М ожно ли процесс вычисления чисел x n продолжать неограниченно, т. е. будут ли числа x n принадлежать отрезку [ a , b ] ? 2) Е сли итерационный процесс (2.3) бесконечен, то как ведут себя числа x n при n ® Исследование этих вопросов показывает, что при определённых ограничениях на функцию j ( x ) итерационная последовательность является бесконечной и сходится к корню уравнения (1.3). Говорят, что функция f ( x ) удовлетворяет на отрезке [ a , b ] условию Липшица, если существует такая постоянная a , что для любых x 1 , x 2 , принадлежащих отрезку [ a , b ] имеет место неравенство: | f ( x 1 ) - f ( x 2 )| a | x 1 - x 2 | (4.3) Величину a в этом случае называют постоянной Липшица. Если функция f ( x ), удовлетворяет на отрезке [ a , b ] условию Липшица, то она непрерывна на нём. Действительно, пусть x 0 – произвольная точка отрезка. Рассмотрим приращение функции f ( x ) в этой точке: D f=f (x 0 + D x ) – f(x 0 ) и оценим его с помощью неравенства (4.3) | D f | a | D x | Таким образом, Предположим, что функция f ( x ) имеет на отрезке [ a , b ] ограниченную производную: | f ( x )| m ; тогда она удовлетворяет условию Липшица с постоянной a = m . Для доказательства этого утверждения воспользуемся формулой конечных приращений Лагранжа: f (x 2 ) – f(x 1 ) = f ( x )(x 2 -x 1 ) (5.3) где x 1 , x 2 , - произвольные точки отрезка [ a , b ] x , - некоторая точка отрезка [ x 1 , x 2 ]. Возьмём модуль обеих частей равенства (4.3) и заменим в правой части | f ‘( x )| на m . В результате получим неравенство (4.3) с a = m . Рис.2.3 даёт геометрическую иллюстрацию установленного свойства. Согласно формуле Лагранжа (5.3) каждой секущей графика функции y = f ( x ) можно поставить в соответствие параллельную её касательную. Поэтому наибольший тангенс угла наклона касательных, и его можно оценить той же константой m : | k | m . Познакомившись с условием Липшица, перейдём к изучению итерационной последовательности, предполагая, что уравнение имеет корень x = c . Существование этого корня можно установить с помощью качественного предварительного исследования уравнения с применением теоремы о существовании корня непрерывной функции. Теорема о существовании корня непрерывной функции Если функция f ( x ) непрерывна на отрезке [ a , b ] и принимает на его концах значения разных знаков, то на этом отрезке существует, по крайней мере, один корень уравнения f ( x ). Теорема о сходимости итерационной последовательности Пусть с – корень уравнения (2.3) и пусть функция j ( x ) удовлетворяет на некотором отрезке [ c - d , c + d ] ( d >0) условию Липшица с постоянной a x 0 на отрезке [ c - d , c + d ] существует бесконечная итерационная последовательность { x n }и эта последовательность сходится к корню x = c , который является единственным решением уравнения (1.3) на отрезке [ c - d , c + d ]. Сформулированная теорема имеет очень простой смысл. Будем говорить, что функция j осуществляет отображение точки x на точку y = j ( x ). Тогда условие Липшица с постоянной a j является сжимающим: расстояние между точками x 1 и x 2 больше, чем расстояние между их изображениями y 1 = j ( x 1 ) и y 2 = j ( x 2 ). Корень c является неподвижной точкой отображения j , он преобразуется сам в себя c = j ( c ). Поэтому каждый шаг в итерационном процессе, сжимая расстояния должен приближать члены последовательности { x n } к неподвижной точке c . После таких соображений поясняющих смысл теоремы, перейдём к её доказательству. Возьмём произвольную точку x 0 на отрезке [ c - d , c + d ] , она отстоит от точки c не больше чем на d : | c - x 0 | d . Вычислим x 1 : x 1 = j ( x 0 ), при этом x 1 - c = j ( x 0 )- j ( c ). Разность j ( x 0 )- j ( c ) можно оценить с помощью условия Липшица: | x 1 - c | = | j ( x 0 )- j ( c )| | x 0 - c | a d . (6.3) Неравенство (6.3) показывает, что x 1 принадлежит отрезку [ c - d , c + d ] и расположен ближе к точке c , чем x 0 . Продолжим построение итерационной последовательности. Вычислим x 2 : x 2 = j ( x 1 ), при этом: | x 2 - c | = | j ( x 1 )- j ( c )| a | x 1 - c | a 2 | x 0 - c | a 2 d Точка x 2 опять принадлежит отрезку [ c - d , c + d ] и расположена ближе к точке c , чем точка x 1 , т.е. мы приблизились к c . По индукции легко доказать, что последующие итерации также существуют и удовлетворяют неравенствам. | x n - c | a n | x 0 - c | a n d (7.3) Отсюда следует, что: Сходимость итерационной последовательности к корню уравнения (1.3) может быть использована для приближённого определения корня с любой степенью точности. Для этого нужно только провести достаточное количество итераций. 4. Быстрота сходимости процесса итераций Используем теперь производную функции j ( x ) для оценки скорости сходимости итераций при решении уравнения х= j ( x ). Нужно оценить скорость, с которой убывают погрешности a n = x - x n приближённых значений х 1 , … , х n , … корня x . Особенно быстро сходится процесс последовательных приближений, если в точке x производная функции j ( x ) обращается в нуль. В этом случае по мере приближения к x , значение j ( x ) стремится к нулю. Так как: | a n + 1 |=| j ( c n )|·| a n | то сходимость процесса ускоряется по мере приближения к точке x . Однако то же самое можно наблюдать в методе Ньютона, при замене f ( x )=0 на Теорема о сходимости метода касательных. Если функция f ( x ) удовлетворяет условиям, сформулированным п.1., то найдётся такое d : 0 d min ( c – a , b – c ), что при любом выборе начального приближения на отрезке [ c - d , c + d ] [ a , b ] существует бесконечная итерационная последовательность (3.5) и эта последовательность сходится к корню c . Доказательство. В силу предположения о дифференцируемости функции f ( x ) и не равенстве нулю её производной f ( x ) уравнение f ( x )=0 эквивалентно на отрезке [ a , b ] уравнению: x= j (x), j (x)=x– f (x)/ f (x) (5.5) так что корень x = c исходного уравнения является одновременно корнем уравнения (5.4). Исследуем возможность отыскания этого корня с помощью итераций. Вычислим производную функции j ( x ): Согласно неравенствам (4.5): Теорема доказана. Требование близости нулевого приближения x 0 к искомому корню c является существенным для метода касательных. На рис.2.5 изображён график, где х 0 выбрано неправильно, то есть расстояние сх 0 >ас, так как ас b с. В результате чего х 1 не принадлежит отрезку [ a , b ], и на этом процесс построения рекуррентной последовательности метода касательных обрывается. Таким образом, до начала расчётов по данному методу для выбора нулевого приближения х 0 нужно знать область локализации искомого корня х=с. Если известен в общих чертах график функции f ( x ), то его легко определить по этому графику. В случае необходимости можно сделать несколько шагов по методу вилки. Затруднения, связанные с предварительным исследованием уравнения, вполне окупаются высокой скоростью сходимости метода. Например, сходимость итераций может быть немонотонной не только вдали от корня, но и малой окрестности корня. Скорость сходимости также изменяется. Его можно оценить, разлагая все функции в (1.7) по формуле Тейлора с центром Следовательно, в методе секущих Поэтому при одинаковом объёме вычисления в методе секущих можно сделать вдвое больше итераций и получить более высокую точность. Что является более приемлемым при численных расчётах на ЭВМ, чем метод касательных. В знаменателе формулы (1.7) стоит разность значений функции. Вдали от корня это несущественно; но вблизи корня, особенно корня высокой кратности, значения функции малы и очень близки. Возникает потеря значащих цифр, приводящая к «разболтке» счёта. Это ограничивает точность, с которой можно найти корень; для простых корней это ограничение невелико. Приводить к общему знаменателю уравнение (1.7) не следует: может увеличится потеря точности в расчётах. От «разболтки» страхуются так называемым приёмом Гарвика. Выбирают не очень малое e , ведут итерации до выполнения | x n + 1 - x n | e и затем продолжают расчёт до тех пор, пока | x n + 1 - x n | убывают. Первое же возрастание обычно означает начало «разболтки»; тогда расчёт прекращают и последнюю итерацию не используют. 8. Метод хорд, или линейной аппроксимации Рассмотрим задачу решения уравнения (1.1) методом хорд. Этот метод состоит в следующем. График функции f ( x ) заменяется её хордой, т. е. отрезком соединяющий концевые точки графика функции f ( x ): точки ( a , f ( a )) и ( b , f ( b )). Абсцисса х 1 точки пересечения этой хорды с осью Ох и рассматривается, как первое приближение искомого корня (рис 1.8). Далее берётся тот из отрезков [ a , x 1 ] и [ x 1 , b ], на концах которого, функция f ( x ) принимает значения разного знака (далее будет показано, что при сделанных предположениях f ( x ) ¹ 0 и , следовательно, такой отрезок всегда существует), и к нему применяется тот же приём; получается второе приближение корня х 2 и т. д. В результате образуется последовательность х n , n =1, 2, … которая, как это будет показано, при сделанных ограничениях на функцию f ( x ), сходится к корню уравнения f ( x ). Легко получить рекуррентные формулы для указанных чисел х n , n =1, 2,… Уравнение прямой, проходящее через крайние точки графика функции f ( x ) имеет вид: Запишем уравнение в виде: y = l (x) Найдём абсциссу х 1 точки пересечения прямой (1.8) с осью Ох, т. е. Решим уравнение l ( x )=0; получим: Предположим для определённости, что f ( x ) и f ( x ) >0, a x b (рис 1.8). В этом случае функция f ( x ) строго монотонна и строго выпукла вниз. Следовательно, любая внутренняя точка хорды, соединяющей крайние точки графика функции f ( x ), лежит над соответствующей точкой графика функции f ( x ), т. е. l (x) > f(x), a > x > b В частности, если х 0 корень уравнения (1.1): f ( x 0 ) = 0, отсюда следует, что l ( x 0 ) > 0 C (3.8) и (4.8) получаем: l (x) = 0, a > x 1 > b Таким образом, l ( x 1 ) l ( x 0 ) (5.8) но линейная функция l ( x ) строго монотонно возрастает, так как l (b) = f(b) > f(a) = l(a) поэтому из (5.8) следует x 1 0 , заменяя теперь отрезок [ a , b ] отрезком [ x 1 , b ] и замечая, что f ( x 1 ) x 1 x 2 x 0 , далее по индукции получим: x 1 x 2 x n x 0 , Таким образом, последовательность { x n }, будучи монотонной, сходится. Пусть lim x n = c , при n ® . Переходя к пределу при n ® в равенстве (4.8) получим f ( c )=0 , т. е. последовательность { x n }сходится к корню уравнения (1.1). Если | f ( x )| ³ m >0, a x b , то не трудно получить оценку погрешности сходимости последовательности { x n }через значения самой функции f ( x ) в точках x n . Действительно, f (x n )= f(x n )- f(x 0 )= f ( x n ) (x n -x 0 ), x n x n 0 , n = 1, 2, …, Отсюда: Существует усовершенствование способа хорд, дающее гораздо более быструю сходимость. В обычном методе хорд мы на каждом шагу используем один из концов отрезка [ a , b ] последнее получившееся приближение. Вместо этого можно использовать два последних приближения – ведь они ближе к искомому корню, чем концы отрезка [ a , b ]. Именно, если x - корень уравнения f ( x )=0, то: |a n+ 1 | |a n - x | S , где Процесс будет сходится к корню уравнения f ( x )=0, причём на каждом шаге он даёт для корня двустороннюю оценку, по которой легко определить достигнутую точность. Сходимость же метода итераций или касательных зависит от того, насколько удачно выбрано нулевое приближение. 3) f ( x ) сложен и требует больших затрат машинного времени, это преимущество становится определяющим. На вопрос о том, какой метод – метод итераций или дихотомия даёт большую скорость сходимости, однозначно ответить нельзя. При методе дихотомии знаменатель геометрической прогрессии убывания погрешности равен q =0.5, а при методе хорд он может принимать значения 0 q Из вышесказанного следует, что ответ на вопрос о наилучшем численном методе решения уравнения не однозначен. Он существенно зависит от того, какую дополнительную информацию о данной функции мы имеем, в соответствие с этим, каким свойствам метода придаём большее значение. При обосновании метода итераций и метода Ньютона на функции j ( x ) и f ( x ), а также на выбор начального приближения х 0 накладывались определённые ограничения. |
оценка коммерческой недвижимости в Брянске
оценка склада в Смоленске