числаки. Название билета и его решение
 Скачать 3.03 Mb.
|
|
№ Название билета и его решение 1 Решение алгебраических и трансцендентных уравнений. Постановка задачи. Способы отделения корней. Метод половинного деления. Метод простой итерации. Метод Ньютона и его модификации (секущих, с рестартом). Метод хорд. Метод обратной квадратичной интерполяции. Нахождение всех корней полинома через сопровождающую матрицу. Постановка задачи и этапы решения. При решении алгебраических и трансцендентных уравнений, встречающихся на практике, очень редко удается найти точное решение. Поэтому приходится применять различные приближенные способы определения корней. В общей постановке задачи обычно требуют непрерывность функции f(x), корни которой ищутся с заданной точностью. Решение при этом разбивается на два этапа: 1.ЛОКАЛИЗАЦИЯ корней, т.е. выделение непересекающихся отрезков, каждый из которых содержит по одному корню. 2.УТОЧНЕНИЕ корней, т.е. вычисление корня на каждом из отрезков с нужной точностью. Первая часть задачи обычно решается либо с использованием примерного графика функции, либо с помощью исследования знака функции и, как правило, не включается в стандартный курс вычислительной математики 1.1 Отделение корня Решение уравнения состоит из двух этапов: 1 – отделение корня, 2 – его уточнение. Отделить корень – значит указать такой отрезок [a , b] , на котором содержится ровно один корень уравнения f(x)=0. Не существует алгоритмов отделения корня, пригодных для любых функций f (x). Если удастся подобрать такие a и b , что 1) f (a) f(b) < 0 (1.2) 2) f ( x ) – непрерывная на [ a , b ] функция (1.3) 3) f ( x ) – монотонная на [ a , b ] функция (1.4) то можно утверждать, что на отрезке [a , b] корень отделен. Условия (1.2) –(1.4) – достаточные условия того, что корень на [a , b] отделен, то есть если эти условия выполняются, то корень отделен, но невыполнение, например, условий (1.3) или (1.4) не всегда означает, что корень не отделен. Корень можно отделить аналитически и графически Графический метод отделения корня Метод половинного деления (или метод вилки) хорошо знаком по доказательству теоремы о промежуточном значении в курсе математического анализа. Его суть заключается в построении последовательности вложенных отрезков, содержащих корень. При этом на каждом шаге очередной отрезок делится пополам и в качестве следующего отрезка берется та половина, на которой значения функции в концах имеют разные знаки. Процесс продолжают до тех пор, пока длина очередного отрезка не станет меньше, чем величина 2. Тогда его середина и будет приближенным значением корня с точностью . Алгоритм данного метода можно записать так: 1.Ввести данные (a, b, ). 2.Если нужная точность достигнута (| b - a | < 2) то иди к п.6 3.Возьми середину очередного отрезка ( С = ( a + b )/ 2 ). 4.Если значения функции в точках а и С одного знака (f(a)*f(C)>0), то в качестве следующего отрезка возьми правую половину (а=С), иначе левую (b=C). 5.Иди к п.2. 6.Напечатать ответ (( a + b ) / 2 ) Метод простых итераций. Перейдем непосредственно к задаче решения уравнения ( ) 0 = x f методом простой итерации, основным моментом которого является сведение исходного уравнения к эквивалентному уравнению вида ) (x x = ( ) ( ) x x x f = = 0 Пусть задача локализации корня уже решена, то есть известно, что единственный корень * x уравнения ( ) x x = находится в отрезке b a, Используя принцип сжатых отображений Банаха, можно построить итерационный процесс ( ) , 2 , 1 , 0 , 1 = = + n x x n n с любым начальным приближением b a x , 0 . Предел последовательности n x будет единственной неподвижной точкой отображения, то есть решением уравнения ( ) x x = , а значит и уравнения ( ) 0 = x f . Однако для этого нужно, чтобы отображение ( ) x в уравнении ( ) x x = было сжатым отображением ] , [ ] , [ b a b a → В общем случае оставляем открытым вопрос о том, как свести уравнение ( ) 0 = x f к виду ( ) x x = так, чтобы отображение ( ) x было сжатым ] , [ ] , [ b a b a → . Однако, если функция ) (x f непрерывна вместе со своей первой производной на отрезке b a, и M x f m ) ( 0 / на b a, , то сведение уравнения 0 ) ( = x f к виду ) (x x = осуществляют следующим образом: 0 ) ( = x f 0 ) ( = x f ) (x f x x + = ) (x x = , где ) ( ) ( x f x x + = , ) ( 1 ) ( / / x f x + = Если в качестве константы взять M 1 − = , то 1 1 ) ( 1 1 ) ( 1 ) ( / / / − − = + = M m x f M x f x , 0 1 ) ( 1 1 ) ( 1 ) ( / / / = − − = + = M M x f M x f x То есть 1 1 ) ( 0 / − = M m k x 1. Докажем сперва, что есть отображение ] , [ ] , [ b a b a → , то есть что для любого ] , [ b a x ) (x также принадлежит ] , [ b a . Так как 0 ) ( / x на отрезке ] , [ b a , то ) (x возрастает на ] , [ b a . Так как b x a * (отрезок ] , [ b a содержит корень * x по предположению), то ) ( ) ( ) ( * b x a [ ) ( ) ( ) ( * * = − = − a x a x по т. Лагранжа ] , [ b a a x a x − − = * * / ) )( ( ] То есть ) (a находится от * x не далее, чем a. [ ) ( ) ( ) ( * * = − = − x b x b по т. Лагранжа ] , [ b a * * / ) )( ( ] x b x b − − = То есть ) (b находится от * x не далее, чем b. Следовательно, ] , [ )] ( ), ( [ b a b a . Так как ] , [ b a x и ) (x возрастает на ] , [ b a , то ) ( ) ( ) ( b x a , то есть )] ( ), ( [ ) ( b a x . А, значит, ] , [ ) ( b a x . Итак, отображение отображает отрезок ] , [ b a в ] , [ b a 2. Докажем теперь, что есть сжатое отображение ] , [ ] , [ b a b a → . По теореме Лагранжа для любых ] , [ , b a y x найдется точка ] , [ b a такая, что | | | ) ( | | ) ( ) ( | / y x y x − = − , то есть ) , ( | ) ( | )) ( ), ( ( / y x y x = Так как 1 ) ( 0 / k x на ] , [ b a , то ) , ( )) ( ), ( ( y x k y x , где 1 0 k . Итак, условие сжатости отображения ] , [ ] , [ b a b a → доказано. Заметим, что если функция ) (x f будет удовлетворять условию 0 ) ( / − − m x f M , то аналогично можно показать, что в качестве коэффициента следует взять M 1 = Метод Ньютона Рассмотрим уравнение ( ) 0 = x f , причем ( ) x f удовлетворяет следующим условиям: ( ) 2 ,b a С x f , ( ) ( ) 0 b f a f , то есть функция ( ) x f принимает на концах отрезка b a, значения с противоположными знаками, производные ( ) x f / и ( ) x f // сохраняют знак в отрезке b a, При этих условиях возможны четыре случая, указанные на рисунках 2.2, 2.3, 2.4, 2.5. Заметим, что на рисунке 2.2 функция ( ) x f возрастает и вогнута, на рисунке 2.3 – убывает и вогнута, на рисунке 2.4 – возрастает и выпукла, на рисунке 2.5 – убывает и выпукла. 1. , 0 ) ( // x f 2. 0 ) ( / x f , 0 ) ( // x f Рис. 2.2. Рис. 2.3. 0 ) ( / x f X Y O x a b=x X Y O x a=x b 3. 0 ) ( / x f , 0 ) ( // x f 4. 0 ) ( / x f , 0 ) ( // x f Рис. 2.4. Рис. 2.5. Примем за 0 x тот конец отрезка b a, , в котором функция ( ) x f имеет тот же знак, что и ( ) x f // . Метод Ньютона, называемый также методом касательных, состоит в следующем. Рассмотрим в точке 0 x касательную к кривой ( ) x f y = , задаваемую уравнением ( ) ( ) ( ) 0 / 0 0 x f x x x f y − + = Положив 0 = y , найдем точку пересечения касательной с осью Ox. ( ) ( ) 0 / 0 0 1 x f x f x x − = Построив касательную в точке 1 x , получаем по аналогичной формуле точку пересечения этой касательной с осью Ox. ( ) ( ) 1 / 1 1 2 x f x f x x − = Продолжая этот процесс, получаем ( ) ( ) 1 / 1 1 − − − − = n n n n x f x f x x Полученная итерационная последовательность является убывающей (возрастающей) и ограниченной снизу (сверху). По соответствующей теореме из анализа эта последовательность имеет предел x . Покажем, что он равен корню уравнения. Перейдем в равенстве ( ) ( ) 1 / 1 1 − − − − = n n n n x f x f x x к пределу, пользуясь непрерывностью X Y O x a=x b X Y O x a b=x ( ) x f и ( ) x f / . Имеем ( ) ( ) x f x f x x / − = . Из последнего равенства следует, что ( ) 0 = x f , то есть * x x = 4. Модифицированный метод Ньютона Рассмотренный выше метод Ньютона требует вычисления производной ) (x f на каждом шаге. В некоторых случаях это может существенно снизить эффективность метода (в смысле затрат машинного времени). Поэтому в тех случаях, когда вычисление производной сопряжено с существенными затратами машинного времени, используют модифицированный метод Ньютона, в котором производная ) (x f вычисляется только в точке начального приближения 0 x : ) ( ) ( 0 1 x f x f x x k k k − = + 2 .19) 5. Метод секущих Еще одна модификация метода Ньютона связана с приближенным вычисление производной ) (x f в окрестности точки k x по формуле 1 1 ) ( ) ( ) ( − − − − k k k k k x x x f x f x f Подставляя это выражение в формулу Ньютона (2.15), приходим к формуле ) ( ) ( ) )( ( 1 1 1 − − + − − − = k k k k k k k x f x f x x x f x x , , 2 , 1 = k , (2.20) которая определяет метод секущих. Название метода связано с его геометрической интерпретацией (см. рис. 2.9). Секущая, проведенная через точки ( ) ) ( , 0 0 x f x и ( ) ) ( , 1 1 x f x , пересекает ось абсцисс в точке 2 x , значение которой определяется формулой (2.20). Для того, чтобы начать итерационный процесс в методе секущих необходимо задать два начальных приближения: нулевое 0 x и первое 1 x . На практике как правило поступают следующим образом: нулевое приближение выбирают аналогично выбору начального приближения в методе Ньютона, а в качестве первого x 1 x 0 x Рис. 2.9. Метод секущих. f(x 0 ) x * f(x 1 ) x 2 приближения выбирают величину + = 0 1 x x , где – заданная точность. Эти значения используются для нахождения последующего (второго) приближения 2 x по формуле (20). Затем, значения 1 x и 2 x используют для определения третьего приближения 3 x и т.д. Для завершения итерационного процесса можно воспользоваться условием (2.14). Метод секущих несколько уступает методу Ньютона в скорости сходимости, однако он не требует вычисления производной ) (x f и поэтому оказывается особенно полезным в тех случаях, когда получение аналитического выражения для производной ) (x f затруднено или невозможно, например, если функции ) (x f получена в ходе численных расчетов, а не задана аналитически. По алгоритму метод секущих близок к методу хорд, однако в отличие от последнего начальные приближения в методе секущих могут располагаться как с разных сторон от корня, так и с одной стороны; кроме того при уточнении корня не проверяются знаки функции ) (x f Метод хорд Этот метод нахождения простых корней широко применяется при решении конечных уравнений. Другие названия рассматриваемого метода: метод ложного положения, метод линейной аппроксимации, метод пропорциональных частей, метод секущих. Идея метода хорд состоит в том, что на достаточно малом промежутке b a, дуга кривой y=f(x) заменяется стягивающей ее хордой. В качестве приближенного значения корня принимается точка пересечения хорды с осью Ox, т.е. это точка x=c. Пусть дано уравнение 0 ) ( = x f , где ) (x f -непрерывная функция, имеющая в интервале ( ) b a, производные первого и второго порядков. Корень считается отделенным и находится на отрезке b a, , т.е. 0 ) ( ) ( b f a f Существуют четыре случая расположения дуги кривой, учитывая значения первой и второй производных: Рассмотрим случай, когда первая и вторая производные имеют одинаковые знаки, т.е. 0 ) ( ' ' ) ( ' x f x f Пусть, например, 0 ) ( ' ' , 0 ) ( ' , 0 ) ( , 0 ) ( x f x f b f a f График функции проходит через точки ) ( , , ) ( , 0 b f b B a f a A . Искомый корень уравнения 0 ) ( = x f есть абсцисса точки пересечения графика функции ) (x f с осью Ox. Эта точка нам не известна, но вместо нее возьмем точку с пересечения хорды с осью Ox. Эта точка x 1 =c является приближенным значением корня. Уравнение хорды, проходящей через точки А 0 и В имеет вид: a b a x a f b f a f y − − = − − ) ( ) ( ) ( а абсцисса ее точки пересечения x 1 =c с осью Ox (т.е. когда = = c x y 0 ) определяется формулой: ) ( ) ( ) ( a f a f b f a b a c − − − = Очевидно, что точка x 1 =c обязательно окажется внутри отрезка b a, , при этом она будет тем ближе к искомому корню, чем меньше кривизна графика функции, а так как кривизна определяется формулой: ( ) 2 3 2 ) ( ' 1 ) ( '' x f x f K + = Точка x 1 =c будет тем ближе к некому корню 0 , чем меньше ) ( ' ' max x f и чем больше ) ( ' min x f на отрезке b a, Замечание Хорда всегда расположена со стороны вогнутости дуги графика и, как видно из приведенных выше рисунков, точки x 1 =c всегда ближе точки x 0 к тому концу отрезка b a, , в котором знак функции ) (x f противоположен знаку ее второй производной f’’(x). Еще один метод, который применяют для поиска корней полиномов, – |