Розв’язок алгебраїчних рівнянь методом послідовних наближень з використанням схеми Горнера

Для знаходження розв’язку алгебраїчних рівнянь степінь яких перевищує два можна також застосувати метод послідовних наближень з використанням схеми Горнера для ділення лівої частини рівняння на , де – дійсний корінь рівняння. У методі послідовних наближень, що застосовуються при вирішенні рівнянь такого типу, відшукується послідовність чисел , яка збігається до числа , яке є коренем рівняння. Ми будемо вважати хорошим наближенням до кореня , якщо залишок від ділення лівої частини рівняння на досить малий. Розглянемо даний процес більш детально. Для цього в рівнянні

відбираємо три останніх члена і знаходимо розв’язок отриманого квадратного рівняння . Якщо корені цього рівняння дійсні, то перерходимо до рішення рівняння , після чого, за перше наближення кореня рівняння (1) приймаємо розв’язок даного рівняння, тобто:

Читати далі

Знаходження найкоротших шляхів в графі методом Шімбелла

Завдяки своєму широкому застосуванню, теорія про знаходження найкоротших шляхів в графі останнім часом інстенсівно розвивається і використовується в різних сферах діяльності, наприклад, для знаходження оптимального матршрута між двома об’єктами на місцевості (найкоротший шлях від будинку до університету), для знаходження оптимального матршрута при перевезеннях, в системах автопілота, в системах комутації інформаційних пакетів в мережі Internet тощо. Найбільш поширені методи визначення зазначених шляхів діляться на дві категорії. Це  індексні та матричні методи.

В основу індексних методів покладено принцип індексації, тобто принцип присвоєння вершинам графа деяких індексів, значення яких змінюються в процесі вирішення. Ці величини в результаті реалізації алгоритму визначають довжину шляху від вихідної до заданої вершини. До індексних методів належать методи Дейкстри, метод Беллмана-Форда, метод Мура та інші.

Всі ж матричні методи пов’язані з побудовою матриці суміжності, елементами якої є довжини відповідних ребер графа. Найкоротші шляхи, в даному випадку, знаходяться послідовним перетворенням цієї матриці. До цих методів належить розглядуваний нижче метод Шімбелла та метод Оттермана.

Читати далі

Топологічне сортування орієнтованого графа методом видалення вершини-джерела

Нагадаємо, що за посиланням топологічне сортування вершин графа нами була розглянута одна з основних задач, що виникає при роботі з орієнтованими графами та один з методів для її рішення.

Задача про топологічне сортуванна графа

Топологічне сортування графа методом видалення вершини-джерела

Сьогодні, для розв’язку задачі такого типу, застосуємо дещо інший алгоритм, заснований на безпосередній реалізації методу зменшення розміру задачі, а якщо бути більш точним, то зменшенням розміру на одиницю.

Основна суть даного алгоритму полягаєв в тому, що на кожній з його ітерацій, здійснюється визначення вершини-джерела орієнтованого графа що залишився (джерелом називається вершина в яку не входить жодне ребро), і, в подальшому, видалення його з усіма, що виходять з нього, ребрами. Якщо таких вершин декілька, довільним чином вибирається одна з них. Порядок видалення таким чином вершин, дає рішення задачі про топологічне сортування. Відмітимо, що якщо на деякому кроці виявиться, що для орієнтованого графа що залишився, вершини-джерела не існує, то задача про тополігічне сортування розв’язків немає.

Читати далі

Застосування методу Крилова для знаходження власних векторів матриці

Метод Крилова, як і метод Данилевського, дає можливість достатньо просто знайти власні вектора матриці, якщо коефіцієнти характеристичного полінома та його коріння визначені. Продемонструємо це і для простоти обмежимося випадком, коли характеристичний многочлен  матриці , має різні корені .

Отже, нехай – вектори, використовувані в методі Крилова для знаходження коефіцієнтів . Розкладаючи вектор за власними векторами матриці отримаємо:

Де – деякі коефіцієнти.

Звідси, враховуючи, що , отримаємо:

Нехай,  – довільна система многочленів. Тоді, складаючи лінійну комбінацію векторів з коефіцієнтами з (3) та в силу співвідношень (1) і (2), знаходимо:

Читати далі

Пошук власних векторів матриці методом Данилевського

Розглянутий в параграфі Пошук власних значень матриці метод Данилевського дає можливість визначати не тільки всі власні значення матриці , а і всі її власні вектори, при умові, що відповідні їм власні значення являються відомими. Покажемо, яким чином це реалізується. Отже, нехай – власне значення матриці , а отже, і власне значення подібної їй матриці Фробеніуса .

Знайдемо власний вектор матриці , який відповідає власному значенню . Для цього, запишемо лінійне рівняння наступного вигляду: . Звідси або у матрично-векторній формі:

Перемноживши матриці, отримаємо систему для визначення координат власного вектора :

Система (3) – однорідна. Рішення її може бути знайдене в такий спосіб. Покладемо . Тоді, починаючи з останнього рівняння, послідовно отримаємо:

Читати далі

Розв’язок задачі комівояжера використовуючи метод подвійного обходу мінімального кістяка

Перш ніж приступити до розгляду чергового способу рішення задачі комівояжера, давайте нагадаємо собі, що собою являє задача такого типу, а також методи, які нами вже було вивчено. Отже, у найпростішому вигляді задачу комівояжера можна сформулювати наступним чином: треба знайти такий найкоротший маршрут по заданих населених пунктах, щоб кожен з них відвідали тільки один раз і кінцевим опинився пункт, з якого починалося подорож. Дану проблему зручно змоделювати за допомогою зваженого графа, вершини якого представляють населені пункти, а ваги ребер визначають відстані між ними. Після цього задача може бути сформульована як задача пошуку найкоротшого гамільтонового циклу деякого графа.

Далі, у вигляді списку, запишемо методи рішення задачі комівояжера, які нами вже було розглянуто і з теоретичною частиною яких можна ознайомитись, перейшовши по відповідному посиланню:

  1. Метод редукції рядків та колонок.
  2. Метод осереднених коефіцієнтів.
  3. Метод Монте-Карло.
  4. Метод найближчого сусіда.

Відмітимо, що одні з них відносяться до категорії точних методів і в якості розв’язку дають оптимальний маршрут, але їх використання являється недоцільним в тому випадку, коли число населених пунктів задачі є достатньо великим числом. Інші – дозволяють швидко отримати рішення задачі комівояжера будь-якої розмірності, але без гарантії його оптимальності.

Читати далі

Знаходження ровз’язку задачі комівояжера методом найближчого сусіда

Виходячи з того, що для більшості комбінаторних задач ефективного способу відшукання оптимального рішення не існує, то в такому випадку, приходять до використання евристичних алгоритми, тобто алгоритмів, які дозволяють швидко отримати рішення, але без гарантії його оптимальності.

Особливий інтерес, з практичної точки зору, представляє процес знаходження ровз’язку задачі комівояжера для великої (близько тисячі) кількості пунктів призначення. В цьому випадку, точні методи рішення задач такого типу не дають бажаного результату, так як вимагають величезних обчислювальних витрат, і процес вирішення займає надто багато часу. Тому на практиці, зазвичай, використовуються евристичні методи, серед яких найбільш використовуваним та відомим являється метод найближчого сусіда.

Основна його суть при розв’язку задачі комівояжера полягає в тому, що пункти призначення послідовно включаються в маршрут, причому кожний наступний пункт, що включається, вибирається таким чином, щоб він був найближчим до останнього вже включеному серед усіх пунктів, ще не включених в маршрут. Основним недоліком даного методу є те, що деякі міста «пропускаються» в ході роботи алгоритму, і в результаті доводиться їх включати в кінці маршруту з більш високими тарифами, що в свою чергу негативно впливає на кінцевий результат (збільшенням довжини маршруту, а відповідно, і затрат на переміщення).

Читати далі

Рішення задачі комівояжера методом Монте-Карло

Методами Монте-Карло називать будь-яку статистичну процедуру, яка використовує статистичну вибірку. Сьогодні застосуємо дану процедуру, для знаходження розв’язку задачі комівояжера. Для цього припустимо, що у задачі комівояжер повинен проїхати міст, і побудувати свій маршрут таким чином, щоб побувати у кожному місті по одному разу і повернутися у початкове. Відмітимо, що, при цьому, витрати на переміщення між містами повинні бути мінімальними.

Отже, для рішення задачі комівояжера методом Монте-Карло, використовується датчик випадкових чисел. Тобто, на першому кроці, серед міст з зномерами (місто з номером один є початковим, тому його вибирати не потрібно) випадковим чином вибираємо по одному місту і запам’ятовуємо їх послідовність. Відмітимо, що в подальшому дана послідовність вважатиметься за оптимальний маршрут. Для цього маршруту розраховуємо функцію мети і також запам’ятовуємо її.

Зауваження: у середовищі програмування delphi, яке ми зазвичай використовуємо для програмної реалізації розглядуваних на даному сайті алгоритмів та методів, існує стандартна функція Random, яка дозволяє програмно формувати випадкові числа. Фактично ця та аналогічні функції в інших мовах програмування є датчиками випадкових чисел.

Читати далі

Розв’язок задачі дробово-лінійного програмування графічним методом

При розгляді теоретичної частини задачі дробово-лінійного програмування, а зокрема, при розгляді конкретної задачі такого типу, нами було анонсовано, що в подальшому дану задачу буде розв’язано з допомогою графічного методу та методу, який базується на зведенні задач з дробово-лінійною цільовою функцією до задачі лінійного програмування. Сьогодні розглянемо перший з них, але перш ніж приступити до розв’язку задачі, розглянемо алгоритм даного методу більш детально. Для цього, припустимо, що нам потрібно знайти максимальне (мінімальне) значення функції мети (де ):

при наступних обмеженнях:

Щоб знайти рішення задачі (1) – (3), спочатку, як і у випадку задачі лінійного програмування, знаходимо багатокутник рішень, який визначається обмеженнями (2) і (3). Припускаючи, що цей багатокутник не порожній, покладаємо значення функції (1) рівним деякому числу :

Читати далі

Чисельне інтегрування функції методом Ромберга

Перш ніж приступити до розгляду чергового методу чисельного інтегрування, нагадаємо, що інтеграл від функції чисельно дорівнює площі криволінійної трапеції, обмеженої графіком цієї функції і межами інтегрування . Відмітимо, що розглядувані на даному сайті методи (метод прямокутниківметод трапецій, метод Сімпсона), базуються на процедурі поділу відрізка  на елементарних частин, після чого, площа криволінійної трапеції обчислюється, як сума площ  прямокутників чи трапецеїдних фігур (в залежності від вибраного методу). Проте, результат отриманий згідно даних методів, сильно залежить від величини кроку (), що позначається на точності обчислення визначеного інтеграла особливо в тих випадках, коли функція має немонотонний характер.

Використання екстраполяції Річардсона, при інтегруванні відомими методами, дозволяє значно скоротити машинний час при незмінній точності результату (оскільки уточнення результату інтегрування не потребує додаткових обчислень функції). Застосування наведеної нижче методики до ітераційної формули трапецій складає розглядуваний метод Ромберга.

Далі, розглянемо основну суть екстраполяції Річардсона. Для цього, вибиремо деякий крок  і розрахуємо по формулі трапецій деяке значення інтеграла . Далі, крок  зменшимо удвічі, в результаті чого, отримаємо нове значення . Тоді, згідно з екстраполяцією Річардсона, розраховане значення інтеграла може бути уточнене за формулою:

Читати далі