Бабенко - Основы численного анализа (947491), страница 6
Текст из файла (страница 6)
Вычисление скалярного произвечения двух вокторов — одна из наиболее частых операций линейной алгебры. Из сказанного ясно, что при выполнении этой операции на ЭВМ возможен значительный рост погрешностей округления. Поэтому целесообразно иметь хотя бы грубые оценки указанных погрешностей. Положим (гго(д З у (' = х1 'З у( сг хя З уз ~ Е гс о=1 Глава 1. Постановка задач чиелютого анализа Предложение 2. Пусть пе < 26(1 —, 6). Тогда с!х Зу — ~ х у < (и + 1) е (1 1!),т г(уЬ, (10) '3=! .1=! где через ~ ,'г обозначена евклидова нора!а вектора. Доклзагильс гво.
Заметим, что в силу соотношения (8) т! З У! Й лг З Уг —.— т!У!(1 -' б1) ч тгуг(1 - бг) .— —. (11) = (х!У!(1 + б!) + Хгуг(1 — бг))(1 †: бг) Положим 8зту З у = ~ ~ уу(1- Ль ); Е- учитывая (9) и (8), получим Ьл! г а г О .,Ор; ~~,,аа-а„)-*ь аь,а а З~)а~6„,! з=! 1=1 Отсюда 1л Ь! 1 =-(1--Лаз)(1.1. без!), у — —. 1, 2, ..., 6, 1 —, Ьь 1, а-! = (1 + бы!)(1 + б! ! ). Поэтому в силу (11) получаем, что 1 ' Ьа! произведение п, сомножителей вида 1 -~- б ( б~ < е); аналогичную структуру.
имеет и выражение 1+ Лаг, а 1 + Л„з при 2 < ! < и является произведением и — у з- 2 сомножителей указанного вида. Учтем о.!евидные неравенства (1 — е)' < П(1+ б,) < (1+ е)'. Поскольку 1п(1+ е) < е, то (1+ е) = екр(11п(1 -'е)) < ехр(1е) = !е (Се) 1 = 1 —, 1е(1 —. — —, — ' ...) < 1 1- 1е 2! 3! ) 1 — 1е,!2 При 1 < и по условию (1 -- 1е/2)-'! < 1 + 6; поэтому (1 л е) < 1 + (1 + 6) 1е. (12) 'З 3, Несколько замечаний а пег*лагки алгоритма По индукции легко доказывается неравенство (1 — )»1 — 1е (13) Таким образом, учитывая сделанные выше замечания о структуре вели- чин гааз и неравенства (12), (13), получим п а «Э т З у — 'у я.
уг (1 — д (и - 2 — ))(1 + 6)".), (14) «=1 «=1 где д ~ < 1 (г —. 1, 2....., и). Неравенство (10) полу гается из соотношения (14) простым применением неравенства Буняковского — Шварца. ьг 3. Ссылки. Конечно, на ЭВМ можно выполнять арифметические операции совершенно точно. Это возможно, когда мы оперируем с целыми либо с рациональными числами. Но при такой работе мы должны использовать соответствующие программы выполнения арифметических операций, вообще говоря, в арифметике многократной точности.
Это увлекательная область арифметики, но мы касаться ее не будем (см. (оеое)). Анализу погрешностей округления задач линейной алгебры посвящен ряд работ. Такой анализ является далеко не простым, и во мпогих случаях он крайне необходим. Объективная оценка вычислительного алгоритма невозможна без анализа роста погрешностей округления, но такой анализ ввиду его трудности делается крайне редко (см.
(39, 148]). 3 3, Несколько замечаний о понятии алгоритма 1. История понятия алгоритма. Слово «алгоритм» (более старая форма «алгорифм») произошло от имени известного ученого 1Х в. Мохаммеда ибн Муса Аль — Хорезми, уроженца Хорезма, являющегося автором знаменитого трактата «КааЪ а1)аЬг вла1 пшцаЬа1а» («Правила восстановления и преобразования»). Алгоритмические методы вычислений бурно развивались, особенно в арабском мире, и зтот прогресс породил замысел построения формальных схем получения 1»ешения определенных классов задач и даже построения формальных схем получения всех истинных высказываний.
Наиболее полную и ясную форму придал зтим замыслам Г. Лейбниц, который писал: «В философии мною найдено средство достичь того же, что сделали Р. Декарт и другие для арифметики и геометрии с помощью алгебры и анализа, но уже для всех наук рег Аг1еш СошЬ1па1ог1аш (посредством Комбинаторики (или Искусства формул) — лат.); она разрабатывалась еще Люллю и П. Кирхером, которые, однако, не смогли проникнуть в ее суть.
Тел«самым указан путь, на котором все существующие составные понятия могут быть разложены на небольшое число простых понятий, являющихся как бы их алфавитом, и посредством правильного метода из комбинаций букв такого алфавита могут быть со временем Глава б Постановка задач численного иа лиза вновь получены все вещи вместе г их теоретическими доказательствами. Это открытие, если только Бог судил л«не его закончить, было бы матерью всех моих открытий и чрезвычайно важным само по себе». Этот отрывок взят из письма !.Лейбница к герцогу Брауншвейгскому — Люнсбургскому, написанного в 1671 г.
Г. Лейбниц на протяжении всей своей жизни занимался уточнением и реализацией своей программы. Для решения алгоритмических проблем он придумал автоматически работающую машину, но эта попытка не привела к цели. В науке долгое время господствовало убеждение, что окончательным решением любой поставленной математической задачи должно быть ее алгоритмическое решение. Знаменитая 10-я проблема Гильберта в своей первоначальной формулировке гласит: «Пусть задано диофантово уравнение с произвольными неизвестныл«и и целыми рациональными коэффициентами. Указать способ, при погиогци которого воззлохсно после конечного числа операций установит»и ризрегиил«о ли это уравнение в целых ра ционильных числахк Когда Д.
Гильберт ставил свою проблему, не возникал вопрос о том,. что такого метода вообще может не существовать. Теперь общий способ„о котором говорит Д. Гильберт. мы понимаем как алгоритм, и саму. проблему можно переформулировать следующим образом: отыскать алгоритм, который по данному многочлену Р(хм .... х„) с целыми коэффициентами позволяет за конечное число шагов узнать, имеет ли этот многочлен корень в целых числах, Убеждение об универсальности алгоритмических методов было подорвано Г. Геделем, доказавшим в 1931 г. алгоритмическую неразрешимость некоторых математических проблем. Позднее были получены результаты о неразрешимых алгоритмических проблемах алгебры; в частности, в 1952 г.
П. С. Новиков доказал алгоритмическую неразрешимость известной проблемы тождества теории групп. Как известно, проблема тождества теории групп состоит в следукэщем: нужно найти алгоритм, который позволял бы для любой группы, заданной конечным числом образующих и соагношений, за конечное число шагов ответить на вощюс, равно ли единице данное слово. записанное с помощью этих образующих. В 50 .60-х годах появился цикл работ М. Дэвиса, Х.
Путнама, Ю. Робинсон и Ю. Матиясевича, которые привели к доказательству отсутствия алгоритма, требуемого в 10-й проблеме Гильберта. Все эти достижения стали возможны благодаря уточнению понятия алгоритма. 2. Предписание. При работе на ЭВМ мы сразу же сталкиваемся с понятием алгоритма и, естественно, нуждаемся в его осмысливании. Для записи алгоритма используются формальные языки, на которых по соответствукэщим синтаксическим правилам записываются инструкции дпя ЭВМ, т. е. программа работы машины. ЭВЛ! используются для решения самых разнообразных числовых задач и для решения широкого класса неарифметических задач; игровых; логических; задач, возникающих в различных областях математики (например, в теории групп, теории чисел и др.); для автоматизации процесса проектирования новых машин 'З 3, Наскол»ко гамсчаиий о иог*лтии алгоритма 27 и механизмов; для черчения чертежей и т.
п. Во всех указанных случаях ЭВМ работает согласно соответствующему предписанию-програмл«е; это предписание и является тем, что мы понимаем интуитивно под словом «алгоритм». Поэтому уточнение понятия алгоритма дает возможность ответить на вопрос что могут делать ЭВМ, или„,чругими словами, какие виды «умственной» работы могут выполнять автоматические вьгзислительные машины'? Ответ на этот вопрос крайне важен, поскольку с ростом мощностей ЭВМ и их повсеместного распространения возникают различного рода «идеи» о всемогуществе ЭВМ (электронных мозгов). на которые можно переложить чуть ли не всю умственную работу, выполняемую человеком. Выше указывался ряд алгоритмически неразрешимых задач и, стало быть, задач, для которых невозможно их машинное решение. Таким образом, чтобы очертить границы областей интеллектуальной деятельности, где возможно автоматическое решение задач, необходимо исследовать различные классы задач на предмет того, возможен ли для них разрешающий алгоритм.
Конструирование алгоритмов для ре«пения отдельных классов задач и исследование их эффективности — одна из наиболее важных задач теории алгоритмов в частности и всей мателгатики в целом. Обычно для интуитивного описания понятия алгоритма указывают ряд его особенностей, таких, например, как конечность, определенность, массовость и т. п. Алгоритм оперирует с конкретными объектами; в ЭВМ это рациональные числа из области Я либо элементы множества ( а. В более общей форме можно считать, что алгоритм оперирует над словами в некотором алфавите. Под алфсгаитпом А = (а, Ь, , х, гг) будам понимать набор конечного числа символов букв; буквы алфавита будем обозначать а» Ь,...,х, р, либо ам ..., асм либо другими символами.
Конечная последовательность букв данного алфавита называется словом (над алфавитом). Так, если (и, Ь, с) . — алфавит,то словами будут аЬЬ, аЬ, Ьа» аЬЬа, Ьс и т.д. Пустая последовательность букв будет определять пустое слово, которое можно обозначать символом А. Множестяо слов над алфавитом Л обозначим через Я(Л), а множество п-членных последовательностей слов -. через В" (Л).
Если на Я(Л) рассмотреть лвуместную операцию последовательного написания слов, то Я(А) станет полутрупной с единичным элементом как Л. Приведем примеры алфавитов, с которыми мы будем работать. Первый алфавит состоит из двух букв (, »). Этот алфавит удобен для изображения систем натуральных чисел. По существу, звездочка -- это разделительный знак. Слова имеют вид (,... ~ либо ~ ,'... » ~ ~...; » ..., где в первом слове число палочек равно и, а второе слово изображает систему.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
