В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 8
Текст из файла (страница 8)
7: Пример интерполяции многочленом, проходящим через три заданные точки36Теперь уже становится понятно, что в общем случае интерполирующая функция будетиметь такой вид: ()() =∑︁ () ==0∑︁=0⏞∏︁⏟ − − =0̸=Она называется интерполяционным многочленом Лагранжа() =∑︁=0∏︁ − − =0̸=Таким образом, получив выше уравнение прямой, проходящей через два заданных значенияв данных точках, мы фактически нашли интерполяционный многочлен Лагранжа первогопорядка.379.Системы линейных уравненийСистема линейных алгебраических уравнений (СЛАУ) – это система вида⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩11 1 + 12 2 + 13 3 + . . .
+ 1 21 1 + 22 2 + 23 3 + . . . + 2 31 1 + 32 2 + 33 3 + . . . + 3 ...= 1= 2= 1...1 1 + 2 2 + 3 3 + . . . + = Здесь количество неизвестных величин совпадает с количеством уравнений и это самыйинтересный вариант, потому что в этом случае система может иметь единственное решение,тогда как в других ситуациях решений может либо не быть (количество неизвестных меньше количества уравнений), либо может быть бесконечно много (количество неизвестныхбольше количества уравнений). Классическим методом решения системы таких уравненийявляется метод Гаусса.9.1.Метод ГауссаВ этом методе для приведения системы к треугольному или ступенчатому виду (когда вкаждом последующем уравнении исключается одна или несколько первых неизвестных переменных) используются элементарные преобразования системы, т.е., такие, при которыхновая система остаётся равносильной первоначальной.
Для этого достаточно, например,таких элементарных преобразований: перестановка любых двух строк; умножение любой строки на ненулевую константу; прибавление к любой строке другой строки.Когда система будет приведена к треугольному виду (если это удастся сделать), можнобудет последовательно (начиная с последних переменных) найти все остальные переменные(так называемый обратный ход алгоритма). Если в системе в процессе преобразованияполучилось невозможное уравнение, то система несовместна, у неё нет ни одного решения.Если одно или несколько уравнений обратились в тождества, это значит, что они являютсяизлишними и их можно убрать из системы.Все эти действия можно проделывать не над всей системой, а только над её коэффициентами (матрица коэффициентов называется матрицей системы), включая также и правыечасти уравнений, т.е., над так называемой расширенной матрицей системы, столбецправых частей в такой матрице далее отчёркнут вертикальной чертой для наглядности.
Если какие-то переменные отсутствуют в некоторых уравнениях системы, в матрице системына соответствующем месте будут находиться нули.Пример 1.Рассмотрим систему:⎧⎨1 + 2 + 321 + 32 + 43⎩31 + 42 + 5338= 4= 13= 17Исключим неизвестную переменную 1 из всех уравнений системы, начиная со второго. Для этого извторого уравнения вычтем первое, умноженное на 2, а из третьего – первое, умноженное на 3.⎛⎞⎛⎞⎛⎞1 1 1 41 1 1 41 1 1 4⎝ 2 3 4 13 ⎠ ∼ ⎝ 0 1 2 5 ⎠ ∼ ⎝ 0 1 2 5 ⎠3 4 5 170 1 2 50 0 0 0Попытка далее исключить из третьего уравнения неизвестную переменную 2 приводит к тому, что втретьей строке расширенной матрицы системы остаются одни нули: третье уравнение превратилось в тождество. Это говорит о том, что это уравнение является излишним; его можно убрать из системы (иливычеркнуть строку из расширенной матрицы). Теперь уравнений стало меньше (два для трёх переменных), для третьей переменной 3 не получится проделать обратный ход метода Гаусса, поэтому во всехуравнениях её проще перенести (с изменением знака) в правую часть и обозначить какой-нибудь другойбуквой (далее используется ); она может принимать произвольное значение.
Для оставшихся переменных1 и 2 проделываем обратный ход метода, выражая через сначала 2 (5 − 2 ), а через её значение —1 (4 − − (5 − 2) = −1 + ). Окончательный результат — система совместна и имеет бесконечно многорешений: 1 = −1 + , 2 = 5 − 2, 3 = ( — любое).Пример 2.Рассмотрим систему:⎧⎨1 + 2 + 321 + 32 + 43⎩31 + 42 + 53= 4= 13= 18При попытке исключения из третьего уравнения второй неизвестной переменной 2 теперь получаетсяневозможное равенство, что свидетельствует о противоречивости системы.⎞⎛⎞⎛⎞⎛1 1 1 41 1 1 41 1 1 4⎝ 2 3 4 13 ⎠ ∼ ⎝ 0 1 2 5 ⎠ ∼ ⎝ 0 1 2 5 ⎠3 4 5 180 1 2 60 0 0 1Система несовместна, решений нет.Пример 3.Рассмотрим систему:⎧⎨1 + 2 + 321 + 32 + 43⎩31 + 42 + 63= 4= 13= 18Прямой ход метода Гаусса успешно завершается: получен треугольный вид системы, а излишних уравненийи противоречивых равенств не возникало.
В последнем уравнении присутствует только одна переменная3 :⎛⎞⎛⎞⎛⎞1 1 1 41 1 1 41 1 1 4⎝ 2 3 4 13 ⎠ ∼ ⎝ 0 1 2 5 ⎠ ∼ ⎝ 0 1 2 5 ⎠3 4 6 180 1 3 60 0 1 1Проделываем обратный ход метода: 3 = 1, далее 2 + 23 = 5, откуда 2 = 5 − 23 = 3, и, наконец, 1 =4 − 2 − 3 = 0. Таким образом, система совместна и имеет единственное решение: 1 = 0, 2 = 3, 3 = 1.Если на каком-то этапе прямого хода метода Гаусса нам надо было исключать очередную переменную, а она уже оказалась исключена ранее (как в примере 1), мы переходимк исключению следующей переменной, ещё оставшейся не исключённой, либо завершаемпрямой ход, если таковых уже не осталось. Если мы не получили «невозможных» равенств(что свидетельствовало бы о несовместности системы), то система совместна и имеет бесконечно много решений; неизвестные переменные, стоящие на первом месте во всех уравнениях, оставляем в левой части (их называют базисными переменными), остальные (ихназывают свободными переменными) — переносим в правую часть с противоположнымзнаком.
Все они могут принимать произвольные значения.Рассмотренные выше примеры достаточно искусственны, в реальности коэффициенты системы могут весьма сильно различаться, а потому важно не допускать чрезмерного влияния ошибок округления в промежуточных вычислениях. Для этого используют выбор39опорного элемента (pivoting ): в качестве опорного элемента берут наибольший по модулюэлемент, причём поиск его и обмен с ним надо производить всегда.Иногда используется также метод полного исключения неизвестных (метод Гаусса-Йордана,неправильно называемый методом Гаусса-Жордана, — поскольку в немецком языке нет буквыЖ). . . Если преобразуется расширенная матрица, то самый правый столбец в конце будетсодержать решение.4010.Динамические данные: способы организации10.1.Общие сведенияВ программировании много технических задач обработки данных решаются выбором правильной структуры данных, которая разработана специально для эффективного решенияименно этой задачи.
Многообразие задач, которые приходится решать в современном программировании обусловило многообразие инструментов их решения.Мы здесь рассмотрим устройство и применение некоторых популярных контейнеров –структур данных, которые предназначены для сохранения наборов данных (иногда – весьма больших) каждый из которых будет оптимальным для решения одного класса задач, нонужно помнить, что для других классов задач будет эффективен совсем другой контейнер.Базовый синтаксис языка Си предусматривает только один статический контейнер – массив, размерность которого известна на этапе компиляции.
Очевидно, что если мы работаемс ограниченным набором однотипных данных, причем ограничение на количество этих данных известно на момент компиляции – то мы можем выделить массив такой размерности,что его заведомо хватит для всего набора. При этом можно завести переменную, котораябудет хранить количество использованных элементов в этом массиве и таким образом наша задача может быть в определенных пределах динамической – количество сохраненныхв массив данных может «плавать» в пределах от нуля до его размерности, указанной приего определении. Очевидно также, что это – паллиативное решение.В общем случае мы не знаем, сколько элементов нам потребуется сохранить (например, потому, что они поступают из внешнего мира – как измерения прибора, ввод от пользователяи т.п.). Конечно, какие-то ограничения на количество сохраняемых данных при этом всеравно существуют в силу ограниченности оперативной памяти компьютера или его жесткого диска, однако, для очень широкого класса задач ресурсов современного компьютерабудет хватать с избытком.Для построения контейнеров, которые могут при необходимости увеличивать свой размер,нужны динамическая память и указатели.
Динамическая память – это память, которуюпрограмма может «попросить» у операционной системы при помощи вызова специальнойбиблиотечной функции (malloc() в языке Си) или специального оператора (оператор newв языке Си++). Если операционная система располагает необходимым количеством памяти, то она вернет нашей программе указатель на выделенный блок памяти необходимогоразмера:#include <stdlib.h>. . .unsigned size = 100;double *A = (double*)malloc(sizeof(double)*size);Указатель нужно понимать как целое число, задающий смещение нужного блока памятиот «начала памяти», то есть – адрес этого блока.
В данном примере мы выделяем блок памяти под столько вещественных чисел, сколько указано в переменной size. Подчеркнём – вотличие от определения статического массива, где мы обязаны задавать константный размер, здесь мы используем переменную, значение которой может быть на этапе компиляциине определено (например, введено пользователем).Если же у операционной системы нет необходимого количества памяти, то она вернёт нам41специальный нулевой указатель (адрес памяти «нулевого байта»), который по соглашениюне может использоваться ни для чего, кроме как для подобных случаев:if (A == NULL) { /* сообщить об ошибке, прервать программу */ }/* можно работать с массивом A */Вся выделенная программе память будет автоматически возвращена операционной системепри завершении программы, однако для эффективного использования ресурсов компьютера выделенную память следует вернуть операционной системе как только она перестанетбыть нужна нашей программе:free(A);В библиотеках языка Си есть также специальная функция, которая меняет ранее выделенный размер блока памяти (увеличивает или уменьшает) – с сохранением тех значенийиз предыдущего блока памяти, которые поместились в новый размер блока памяти:size *= 2;A = (double*)realloc(A,sizeof(double)*size);10.2.Динамический массив (вектор)Мы видим, что даже для простейшей динамической структуры данных, которой являетсядинамический массив, нам необходимо поддерживать как минимум две связанные переменные: указатель начала массива (А) и размер нашего массива (size).Чтобы хранить, а главное, передавать в функции такие связанные переменные вместе,удобно использовать структуры языка Си:struct array {double* A;unsigned size;};В языке Си++ удобнее использовать классы, которые определяют как единое целое нетолько данные, которые надо сохранить, но и функции для работы с ними.Итак, динамический массив – это совокупность однотипных элементов, занимающих смежные области памяти.
Это самая экономная динамическая структура данных – этот контейнер не тратит никакой дополнительной памяти сверх необходимой для хранения одногоэлемента.Давайте посмотрим на типичные операции с данными, которые должен поддерживать любой контейнер: вставка элемента, удаление элемента, поиск элемента по его значению. Прокомментируем производительность, с которой выполняются эти операции.Самая элементарная операция с элементом массива – это прочитать или записать его позаданному индексу:42A[i] = 9.8;Такая операция не зависит от количества элементов в массиве, её выполнение занимаетконстантное (и при этом очень малое) время.Вставка элемента в произвольное местоXмассива – это операция, линейно зависящая от размера массива. Мы должны выделить память нового размера (на один элемент больше), скопировать начало массивадо точки вставки, скопировать новый элеXмент, скопировать остаток массива послеточки вставки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
