1611141236-738b6049e710338c8c4dd43e7bd2b717 (824981), страница 6

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

Текст из файла (страница 6)

В теоретических исследованиях, однако, первостепенное значение приобретают формулировка условий совместности или определенности линейной у Я. Сисшемы линейных уравнений. Первые шаги 27 системы, а также нахождение общих формул для решений в терминах коэффициентов и свободных членов без приведения системы к ступенчатому виду. В какой-то мере одному из этих требований отвечает следствие 1'.

П р и и е р 1. Вновь обратимсл к задаче о нагретой пластинке из 1 2. Как мы видели в п. 1, интересующий нас вопрос выражается в свойствах вполне конкретной линейной системы (для определенности назовем ее НП) с довольно большим числом неизвестных во Следуя критерию, сформулированному в следствии 1', рассмотрим однородную линейную систему (ОНП), вссопиированную с НП. Другими гловамя, температура всех граничных точек пластинки принимается теперь равной нулю. Пусть е — номер внутренней точки с максимальным значением )зп).

Тогда из условия 1 + се+ Се+ ел 4 вытекает )1,) = )сп( = )зь) = )зс( ж )зя). сдвигаясь на один шаг решетки в любом из четырех направлений, мы будем проходить через точкя с тем же значением (гб = ~1,(, пока не достигнем граничной точки с нулевой температурой. Значит, )зп( = О, а поэтому и Ц = 0 для всех 4. Итак, система ОНП имеет лишь нулевое решение, и, стало быть, НП вЂ” совместная и определенная линейная система. Задача о нагретой пластинке в первоначальной ей постановке тем самым решена. Пример 2. Дана линейная система — 1 =1, =О, хг хз — х~ — хз +хз хп-з — хп-1 + хп = О.

Очевидно, что это — совместная определенная система, уже приведенная к ступенчатому (треугольному) виду. Только, решая ее, нужно двигаться не снизу вверх, а сверху вниз. Решением является по определению последовательность первых и чисел Фибоначчи Уыуз,...,/и.

Эти числа связаны с одням ботаняческим явлением, так называемым филлошаисисом (расположением листьев на растениях). Однако при и = 1000 или даже при пронзвольном и хотелось бы указать общее выражение (аналитическую формулу) для и-го числа Фибояаччи. Вы можете возразить, сказав, что у ввс хватит терпения указать и узосо, следуя индуктивному определению этих чисел. Но это не будет математическим решением вопроса. В гл. 2 и гл.

3 мы укажем два выражения длл уп, хотя, конечно, эту конкретную задачу можно решить и более прямыми средствами. Замечание 1. Иногда бывает удобнее находить решения линейной системы, не приводя ее к ступенчатому виду. Это особенно относится к тому случаю, когда матрица системы содержит много нулей. Небольшая практика здесь предпочтительнее длинных объяснений. 3 ам е ч ан не 2. Какое количество Г„арифметических операций необходимо выполнить для решения системы и линейных уравнений с и неизвестными методом Гаусса? Это не праздный вопрос, поскольку ставшему обыденным в наши дни использованию ЭВМ при больших и должны предшествовать априорные оценки машинного времени, требуемого для решения задачи.

28 Гл. 1. Истоки алгебры Так как умножение двух чисел более трудоемко, чем сложение, то рекомендуется подсчитывать только количество умножений и, разумеется, делений, называемьпс далее просто операциями. Без ограничения общности можно предполагать, что решение линейной системы единственно, т.е. все неизвестные — главные.

Правые части уравнений пока игнорируем. Тогда для исключения неизвестной х1 из уравнения с номером 1 > 1 нужно заготовить число )е = ае1/аы (одно деление) и вычислить еще п-1произведений (еаеч у' = 2,3,...,п, т.е. всего требуется и операций. Процедурой вычитания из 1-го уравнения первого, умноженного на 16 мы условились пренебречь. Так как 1 = 2, 3,..., и, то для исключения х1 понадобилось п(п — 1) операций. На втором шаге, когда мы имеем дело с системой порядка п — 1, понадобится (и — 1)(п — 2) операций, на третьем — соответственно (и — 2)(п — 3) и т.д. Общее число операций для приведения левых частей системы к треугольному виду (5) равно сумме Г(п) = п(п — 1) + (и — 1) (и — 2) +...

+ 1(1 — 1). Нетрудно убедиться (докажите сами или загляните в Э 7), что пг — и Г(п) = —. 3 Процесс нахождения компонент хи, ха „..., хо решения (движение снизу вверх по системе (5)) требует всего 1+ 2+ 3+... + и = п(п+ 1) 2 операций. При больших и это не внесет существенного вклада в общую сумму операций.

Итак, вполне удовлетворительной оценкой числа операций является (гауссова) величина Г„= пз/3. В 1969 г. Штрассеном разработан метод (подробности см. в [ВА П]),требующий только Ш С „~оггг С пг,г1 операций, — значительный выигрыш при очень больших и, полученный, правда, за счет увеличения числа операций сложения.

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

При этом важны не только сами алгоритмы, но и оценки их сложности. Определитпкпи неболыпих порядков 29 3 4. Определители небольших порядков Излагая метод Гаусса, мы не слишком заботились о значениях коэффициентов при главных неизвестных. Важно было лишь то, что эти коэффициенты отличны от нуля. Проведем теперь более аккуратно процесс исключения неизвестных хотя бы в случае квадратных линейных систем небольших размеров. Это даст нам пишу для размьпплений и исходный материал для построения общей теории определителей в гл. 3. Как и в 3 3, рассмотрим систему двух уравнений с двумя неиз- вестными апх1+ аггхг = О1, аюх1+ аггхг = бг ~ аг1 агг ~ Тем самым квадратной матрице сопоставляется число ап агг ~ = апагг — агга12 О21 О22 (2) Если мы попытаемся исключить хг из системы (1), умножив первое уравнение на агг и прибавив к нему второе, умноженное на — амп то получим ап а12 )х1 = огагг — ога12.

ам агг Правую часть также можно рассматривать как определитель матри О1 агг 9 !ап аш цы ~! г. Предположим, что ~ ~ ~ О. Тогда мы имеем Ьг огг О21 О22 (3) Имея формулы для решения системы двух линейных уравнений с двумя неизвестными, мы можем решать и некоторые другие системы (решать системы — значит находить их решения). Рассмотрим, и постараемся найти общие формулы для компонент х~1, хг ее решения.

ап агг Назовем определишелем матрицы ~~ ~~ выражение апагг— ам агг — аггагг и обозначим его Гл. 1. Истпоки алгебры ЗО например, систему двух однородных уравнений с тремя неизвестными амх«+ а«гхг + а«зхг = О, (4) амх1 + аггхг + аггхз = О. Нас интересует ненулевое решение этой системы, так что хотя бы одно нз х«не равно нулю. Пусть, например, хг ~ О. Разделив обе части на — хг и положив у1 = — х«/хг, уг = — хг/хг, запишем систему (4) в том же виде апу« + аггуг = а«з, а2191 + «122У2 а23 что и (1).

При предположении ! 12 ! ф О формулы (3) дают аы а«г а21 а22 аы агг аы агг ! аы агг а21 а22 Неудивительно, что мы нап«ли из системы (4) не сами х1, хг, хг, а только их отношения: из однородности системы легко следует, что если (хе хге, хег) — решение и с — любое число, то (схе1, схге, схге) тоже будет решением. Поэтому мы можем положить и сказать, что любое решение получается из указанного умножением всех х«на некоторое число с.

Чтобы придать ответу несколько более симметричный вид, заметим, что всегда как это непосредственно видно из формулы (2). Поэтому (5) можно записать в виде Эти формулы выведены в предположении, что ! ам агг ! ~ О. Неаю агг трудно проверить, что доказанное утверждение верно, если хоть один из входящих в выражения (6) определителей отличен от нуля.

Если же все три определителя равны нулю, то, конечно, формулы (6) дают решение (а именно нулевое), но мы не можем утверждать, что а«г х1 ! агз У1 = хз !ам а21 агг ! агг ! ., ! Уг = — — = з зо 4. Опредеоипгели небольших пор*двое все решения получаются из него умножением на число (рассмотрите систему, состоящую иэ двух совпадающих уравнений хг+хг+хз = О). Перейдем теперь к случаю системы трех уравнений с тремя неизвестными амхг + аггхг + агзхз = О, агзхз + азгхг + агзхз = 0 аззхз + азгхг + аззхз = О. Мы хотим исключить из этой системы хг и хз, чтобы получить значение для х1.

С этой целью умножим первое уравнение на см второе на сг, третье на сз и сложим их. Подберем сю сг, сз так, чтобы в получившемся уравнении члены с хг и хз обратились в нуль. Приравнивая нулю соответствующие коэффициенты, мы получим для сы сг и сз систему уравнений агзсг + аггсг + азгсз = О, аззсг + агзсз + аззсз = О, относящуюся к тому же типу, что и (4). Поэтому можно взять ( агг азг ~ ( агг азг ! ~ агг агг ~ После очевидных изменений мы получаем для хд выражение = 6 азг агз — Ь азг агз Ь агг азз (7) 1 азз азз 1 ~ азг азз 1 агг агз Коэффициент при хз называется определшпелем матрицы ам агз агз агз агг агз азз азг азз и обозначается аы азг азз азз агг агз аы азг азз Таким образом, эа определитель третьего порядка мы берем выра- Гл.

Характеристики

Список файлов книги