История и методология прикладной математики. Русанов, Росляков (2004) (1185895), страница 21
Текст из файла (страница 21)
Методом Лвгренжв были вмчнслены несколько тысяч элементов разложен л 2 В яя в непрерывную дробь числа чг2. Вычисления выполнялись нв ЭВМ БЭСМ-б по специально Р рогрвмме, оперирующей с целыми числвми, содержчщнмн до 6000 десятичных знаков. Результаты этих расчетов постввнли под сомнение, достоверность гипотезы. И з способов решения алгебраических уравнений не треб Э ую-, щих знания приближенных значений корней, которые часто при-' меняются на практике, следует еще отметить метод спуска и метод парабол.
Пусть л = ~/иэ+ 02. Если найдено некоторое приближение хь, уь к точке минимума функции Р(х, р), то в методе скорейшего спуска следующее приближение хь+ю рь+, находится на прямой, направленной по вектору йгадГ(хь,уь). Выбирая функцию со 1 э виде у = -(из + еэ) или сэ = ь~аз+ нР, методу определения 2 хьсю рььз можно придать вид метода Ньютона. Метод парабол, также не требующий приближенных значений корней уравнения (10.19), состоит в следующем. Пусть заданы числа ль 2, ль д, ль, действительные или комплексные. По этим точкам строится интерполяционный многочлен Лагранжа второй степени для Р„(л) .
Корень этого многочлена, ближайи|ий к лю берегся за льзю Такая же процедура проделывается тля узлов ль ю лю льью и ближайший к ль+г корень полученного уравнения второй степени берегся за айвз. Продолжая процесс, получаем последовательность точек, сходящуюся к некоторому корню уравнения (10.19). 4. Многие методы, например, методы Ньютона и Лобачевского, позволяют вычислять как действительные, твк и комплексные корни. Однако в случае комплексных корней алгоритм может существенно усложнятьсн.
Поэтому стали разрабатываться специальные методы для отыскания комплексных корней. Методы спуска и парабол осуществляют отыскание и действительного и комплексного корня по единому алгорятму. В случае действительного многочлена (10.13) комплексные корни попарно сопряженные и каждая пара образует действительный квадратный трехчлен, Часто сказывается удобным метод последовательного выделения квадратных множителей для определения комплексных корней алгебраического уравнения (10.13).
Вариант такого метода был разработан Хичкоком (1938). Суть его состоит в следующем. Обозначим искомый трехчлен тлг(х) — = х +рх+ 0 с неизвестными пока р и а и разделим на него Р„(х). Имеем Р„(х) = (хз -ь рх -с 0)Р„2(х) -ь хР(р, 0) -ь Я(р, 0), где Р(р,а) и Я(р,б) — многочлены от р и 0. Для того чтобы т2(х) был делителем Р„(х), необходимо и достаточно выполнения условий Р(р 0) = 0 д(р 0) = 0.
— 101— Хичкок определяет р и о из этой системы методом Ньютона, При этом частные производные от Р и Я по р и о находятся с использованием двукратного деления Р„(х) на газ(х). Рядом. математиков этот метод был распространен на случай множителя произвольной степени. 5.
Развитие методов решения уравнений падает, в основном,. на вторую половину прошлого столетия, когда появилясь ЭВМ.,: Это характерно вообще для вычислительной математики, раз-' витие которой шло параллельно с развитием вычислительной' техники. Оно стимулировалось необходимостью решать новые. прикладные задачи, возникающие в науке и технике, на имеющейся вычислительной базе. Произошла переоценка многих ранее разработанных методов, в том числе и методов нахожде-.' ния корней уравнений.
Методы, созданные в домашинную эпоху,:; для которых характерно сокращение рутинных вычислений за; счет более интеллектуального вмешательства исследователя в процесс вычислений, часто оказываются сложными для реализации на ЭВМ. 'Гак, метод Лобачевского-Греффе редко используется при расчетах на ЭВМ. Метод Бернулли был специально модифицирован рядом математиков с учетом особенностей работы на ЭВМ. Выбор того или иного метода вычисления корней уравнения 1(х) = 0 зависит ат многих факторов: от вида функции У(х) (алгебраическая или трансцендентная), от ее дифференциальных свойств, от наличия хорошего начального приближения. Важно также, какая доля вычислений при решении задачи падает на вычисление корней уравнения. Когда /(х) — трансцендентная функция, часто ее анализ бывает затруднен и для вычисления корней применяется простейший медленно сходящийся, но абсолютно надежный метод половинного деления (бисекции). Он заключается в том, что на каждой итерации отрезок, содержащий корень, делится пополам и в качестве нового отрезка берется та половина, в которой содержится корень.
Приведем элементарный пример использования метода половинного деления и метода Ньютона для определения корня уравнения 1(х) = О. Пусть на отрезке (О, 1] имеется единственный корень сг, и задано начальное приближение хо такое, что (хе — а) — 0.1. Применяя метод Ньютона, получаем последовательно хы хз, хз, причем )х~ — а( — 10 ~, (хз — а! ш 10 4, ~тз — а( — 10 в.
При этом нужно будет три раза вычислить значения Дх) и 1'(х). При использовании метода деления пополам потребуется для получения той же точности проделать п итераций, где п определяется из условия 10 в ш 2 ", что дает и ш 26. При этом функция 1"(х) вычисляется 26 раз. Если на ~ ычисление требуется ~'(х)такое же число операций, что и на вычисление 1(х), то во втором случае объем вычислений будет е 4-6 раз больше. Преимущество одного из методов определянгя объемом программы вычисления 1'(х) н тем, какой процент операций в общей программе приходится на вычисление корня уравнения 1 (х) = О. Если он мал, то преимущество метода половинного деления очевидно. 6. Некоторые из методов, разработанных дли решения одного э равнения, обобщены на случай систем уравнений Ях,,хз,...,х )=О, 1=1,2,...,т.
(10.20) Одним из таких методов является метод скорейшего спуска 1адача определения корней системы (10.20) сводится к задаче определения точек минимума некоторой функции, например, Р(хыхз,...,х ) =~ 1",(хг,хы...,х ), ° си которая принимает минимальное значение Г =- О во всех точках, удовлетвориющих системе (10.20). Если известно некоторое приближение к точке минимУма хв = (хы хю..., х ), то следУющее приближение х~+' ищется в направлении наибольшего убывания функции Е, т. е.
в направлении антигрэдиента Е. Часто используют более простой метод покоординатного спуска. Запишем систему (10.20) в векторной форме 1(х) = О, (10.21) где х = (хмхз,...,х ), 1 = Щх~),Яхт),...„1(х„„)) . Простейшим итерационным методом решения системы (10.21) является метод простой итерации. Если (10.21) представить в виде х =. ~р(х), — 102 — 103— то метод простой итерации есть итерационный процесс хе+~ = ~р(х"), хп — задано. Он сходится, когда какая-либо из норм матрицы Л =.. /дУ<'1 — 1.дхуу меньше единицы. Метод Ньютона для системы (10.21) имеет вид х"+ = х" — У '(х")7(х"), х — — задано, (10.22) где Г ' — матрица, обратная матрице 7, элементами которой дЛ явлюотся производные — ', г, г' = 1, 2,..., гп. Если начальное дх1 приближение хл достаточно близко к корню, то метод Ньютона сходится.
Сходимость метода квадратичная. Основное время при вычислениях по формуле (10.22) тратится на обращение матрицы / (х"). Для сокращения этого времени матрицу 7 '(х"), вычисленную на (и+ 1) -ой итерации, используют не только для вычисления х +, но и нескольких следующих приближений. Можно один раз вычислить 1 '(хв), и приближения по форму; ле (10.22) находить при постоянной матрице. При этом скорость схоцимости процесса замедлится, но общий выигрыш во времени может быть большим. 9 11. Решение задач линейной алгебры 1.
Линейнал алгебра охватывает обширный круг задач, свя-' занных с исследованием объектов, обладающих свойствами ли-' нейности. Мы рассмотрим здесь два типа задач из этой обла-' сти — решение систем линейных уравнений и вь|числение соб-': ственных значений матриц. Практическая необходимость решения уравнений с числом' неизвестных более одного вызвала появление методов подсш-' новки и исключения неизвестных задолго до возникновения ал-: гебраической символики. Примером может служить знаменитая задача Архимеда о быках, в которой он предлагает найти восемь- целых чисел, удовлетворяющих семи линейным уравнениям и: дополнительным нелинейным условиям.
Решение подобной за.- ', дачи предполагает знакомство с методом исключения. Методом- исключения широко пользовались арабы н средневековые европейские математики. Однако общие методы решения систем липейных уравнений могли быть созданы только после развития алгебраической символики и введения в математику отрицательных чисел. Следует, однако, отметить, что в Древнем Китае еще ло начала Новой Эры был известен регулярный метод исключения с помощью действий над элементами таблицы коэффициентов системы и правых частей по правилам современной теории определителей.
Понятие определителя было фактически введено в 1693 году Лейбницем в его письме к Лопиталю. Здесь он также впервые ввел двузначные обозначения для коэффициентов линейной : истемы. Приведя пример трех линейных уравнений, он указал алгоритм вычисления ее результата, который в современной терминологии является определителем системы. Однако дальяейшего развития теория определителей в работах Лейбница не получила. В 1750 году швейцарский ученый Габриель Крамер, не зная о письме Лейбница, сформулировал в законченном виде закон образования решений системы любого числа линейных уравнений. Он ввел понятие "беспорядка" в перестановках коэффициентов и дал правило определения знаков при отдельных членах, входящих в выражения для неизвестных.
Крамера обычно называют изобретателем определителей, у него не хватало только удобного обозначения для их записи я вычисления. Этот шаг был сделан Вандермондом в 1772 году в работе "Об исключении". Он предложил специальный символ для определителя. Однако его обозначения были еще далеки от г современных.
11апример, элемент матрицы а, он обозначал — . У' Крамером было сформулировано правило, носящее его имя, для вычисления решения системы линейных уравнений: если определитель системы отличен от нуля> то значение любого неизвестного равно отношению определителя, который получается из определителя системы заменой столбца, соответствующего этому неизвестному, столбцом свободных членов, к определителю системы. Таким образом, Крамером было установлено, что необходимым и достаточным условием разрешимости системы и линей- — 104— — 105— ных уравнений с п неизвестными является неравенство нулю ее определителя. Исследованием свойств определителей и линейных систем занимались многие ученые.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
