Розробка програми 'Вирішення задачі методом найменших квадратів'
МІНІСТЕРСТВО АГРАРНОЇ
ПОЛІТИКИ
ПОЛІТЕХНІЧНИЙ КОЛЕДЖ ЛНАУ
Відділення: Енергетика та
комп'ютерні системи
ПОЯСНЮВАЛЬНА ЗАПИСКА
До курсової роботи
Тема: «Розробка програми “Вирішення задачі методом найменших
квадратів”»
Луганськ 2011
РЕФЕРАТ
Курсова робота містить 28 сторінок формату А4, 3 малюнка, 1
блок-схему, один додаток.
Мета даної курсової роботи - створення програми, яка дозволяє
полегшувати вирішення завдань методом найменших квадратів. Курсова робота
служить для вивчення принципів програмування, а також вивчення мови
програмування С++ і бібліотеки класів MFC.
Ключові слова:
ФАЙЛ, ПРИКЛАДНІ ПРОГРАМИ, ФУНКЦІЯ, ІНТЕРФЕЙС, ЗМІННА,
АЛГОРИТМ, СТРУКТУРИ, ПОКАЖЧИКИ, ЗМІННА, КНОПКА, MFC, КЛАС, ФУНКЦІЯ, ЦИКЛ,
ОБРОБКА ПОДІЇ
ЗМІСТ
ВСТУП
. ТЕОРЕТИЧНА РЕАЛІЗАЦІЯ
.1 Технічне завдання
.2 Ескізний проект
.3 Технічний проект
. ПРАКТИЧНЕ РІШЕННЯ
.1 Робочий проект
.2 Реалізація алгоритму
.3 Інтерфейс програми
ВИСНОВОК
СПИСОК ЛІТЕРАТУРИ
ДОДАТОК
ВСТУП
З моменту виникнення обчислювальній техніці виникло і
програмування. У міру розвитку обчислювальної техніки виникали різні методики
програмування. На кожному етапі створювався новий підхід, який допомагав
програмістам справлятися з ускладненням програм, що росло. Перші програми
створювалися за допомогою ключових перемикачів на передній панелі комп'ютера.
Очевидно, що такий спосіб підходить тільки для дуже невеликих програм. Потім
була винайдена мова асемблера, який дозволяв писати довші програми. Наступний
крок був зроблений в 1950 році, коли була створена перша мова високого рівня
Фортран. Використовуючи таку мову, програмісти могли писати програми до
декількох тисяч рядків завдовжки. Для того часу вказаний підхід до
програмування був найбільш перспективним. Проте мова програмування, що легко
розуміється в коротких програмах, коли справа стосувалася великих програм,
ставала нечитабельною (і не керованим). Позбавлення від таких неструктурованих
програм прийшло після винаходу в 1960 році мов структурного програмування
(structured programming language). До них відносяться мови Алгол, Паскаль і Сі.
Структурне програмування включає точно позначені структури, що управляють,
програмні блоки, автономні підпрограми, в яких підтримується рекурсія і
локальні змінні. Суттю структурного програмування є можливість розбиття
програми на складові її елементи. Використовуючи структурне програмування,
середній програміст може створювати і підтримувати досить складні і великі
програми.
Хоча структурне програмування, при його використанні для
написання помірно складних програм, принесло видатні результати, навіть воно
виявлялося неспроможним тоді, коли програма досягала певної довжини.
Щоб написати складнішу програму, потрібний був новий підхід
до програмування. У результаті були розроблені принципи об'єктно-орієнтованого
програмування (ООП). Об'єктно-орієнтоване
програмування - це порівняльно новий підхід до створення програм. Він акумулює
кращі ідеї, втілені в структурному програмуванні, і поєднує їх з могутніми
новими концепціями, які дозволяють оптимально організовувати написані програми.
Об'єктно-орієнтоване програмування дозволяє програмістові розкласти проблему на
складові частини. Кожна частина стає самостійним об'єктом, що містить свої
власні коди і дані, які відносяться до цього об'єкту. В цьому випадку вся
процедура в цілому спрощується, і програміст дістає можливість оперувати з
набагато більшими за об'ємом програмами.
Всі мови ООП, включаючи С++, засновані на трьох
основоположних концепціях, званих інкапсуляцією, поліморфізмом і спадкоємством.
С++ - це універсальна об'єктно-орієнтована мова
програмування. C++ є мовою "спілкування" людини з комп'ютером.
Метою даної курсової роботи було написання програми-довідника
меломану, людина яка збирає музику, використовуючи об'єктно-орієнтований підхід
і засоби програмування під Windows і це було досягнуто за допомогою пакету
Microsoft Visual Studio 6.0 і мови програмування С++.
Дана курсова робота, а саме, програма, що розробляється в
ній, присвячена створенню програми, що працює з базою даних, яка зберігає
інформацію про вищі навчальні заклади, а саме їхню адресу, спеціальності,
іспити, конкурс, вартість контрактного навчання.
У програмі, що розробляється в курсовій роботі, зачіпаються
проблеми, зберігання, видалення, пошуку та додаванням нових даних в базу даних,
яка є файлом текстового формату, що зберігає інформацію.
У даній роботі використовується пошук необхідної інформації
по заданому користувачем параметру, видалення непотрібної інформації. Ця
програма належить до різновиду прикладних програм користувача.
1.
ТЕОРЕТИЧНА РЕАЛІЗАЦІЯ
1.1
Технічне завдання
Завданням курсової роботи було написати програму «Вирішення
задачі методом найменших квадратів», яка дозволяє вирішувати важкі задачі на
знаходження коефіцієнтів при невідомих.
Таким чином, сформулюємо ряд вимог до
нашої програми:
• необхідно розробити вид звичайного
програмного продукту з кнопками і полями вводу та виводу.
• програма повинна мати простій
інтерфейс, інтуїтивно зрозумілий користувачеві.
• програма повинна споживати мінімум
ресурсів комп'ютера.
• початковий код програми повинен
мати модульну структуру, докладні коментарі для можливості доопрацювання іншими
програмістами.
1.2
Ескізний проект
Зовнішній вигляд програми - вікно, яке має поля для введення
початкових параметрів і виведення результату, кнопку при натисканні котрої
проводиться розрахунок завдання.
Для написання програми був вибраний Microsoft Visual C++.
Microsoft Visual C++ є інтегрованим середовищем розробки, в якій ви можете
легко створювати, відкривати, переглядати, редагувати, зберігати, компілювати і
відладжувати всі свої доповнення, написані на С або C++. Перевагою цього
середовища є відносна простота і легкість у вивченні. Переважна більшість
програмних продуктів світового класу створена з використанням середовища
розробки Microsoft Visual C++.C++ - це найефективніший і високопродуктивний
засіб розробки програм на мові C++ для операційної системи Windows. За
допомогою системи Microsoft Visual C++ 6.0 Professional Edition можна отримати
такі переваги, як можливість створення надійних компонентів, могутні засоби
розробки баз даних і повну підтримку для Інтернету, що дозволяє створювати
стратегічно важливі програми.
Як додатковий засіб розробки можна використовувати бібліотеку
класів MFC.- розшифровується як Microsoft Foundation Classes. При розробці
даного продукту дотримувалися строгих правил і стандартів. Основні принципи, на
яких базується MFC, перераховані нижче:
· можливість комбінувати звичайні виклики функцій з
використанням методів класів;
· баланс між продуктивністю і ефективністю базових класів;
· спадкоємність в переході від використання API-функцій
до бібліотеки класів;
· простота перенесення бібліотеки
класів на різні платформи: від Windows3.1 до 'Windows 95/NT, потім до Windows98
і т.д.;
· органічний взаємозв'язок з
традиційними засобами програмування на C++, що дозволяє уникнути надмірного
ускладнення програмного коду.
Розробники бібліотеки усвідомлювали, що від досконалості її
програмного коду залежить ефективність роботи додатку, заснованого на MFC.
Чітко дотримувалися вимоги до розміру класів і швидкості виконання їх методів.
В результаті за швидкістю роботою класи MFC нічим не поступаються бібліотечним
функціям мови С. При створенні MFC також враховувалася можливість роботи в
змішаному режимі.
Ще одна важлива властивість, на яку звертали увагу розробники
Microsoft, - це можливість безпосереднього використання базових класів в
програмах. У Microsoft їх називали "важкими класами", оскільки
засновані на них доповнення відрізнялися великим розміром програмного коду і
недостатньо швидко виконувалися. Розробникам MFC вдалося знайти золоту середину
між розумним рівнем абстрактності і розміром коду.
Нижче перераховані основні достоїнства бібліотеки MFC.
Розширена система обробки виняткових ситуацій, завдяки якій
програмні продукти менш чутливі до помилок і збоїв. Помилки типу "брак
пам'яті" обробляються автоматично.
Покращувана система діагностики, що дозволяє записувати у
файл інформацію про використовувані об'єкти. Також сюди слід віднести
можливість контролю за змістом змінних-членів.
Повна підтримка всіх API-функцій, елементів управління,
повідомлень, GDI, графічних переваг, меню і діалогових вікон.
Можливість визначити тип об'єкту під час виконання програми.
Це дозволяє здійснювати динамічне управління змінними-членами у разі
використання різних екземплярів класу.
Невеликий розмір і швидкість виконання програмного коду
класів.
Професійний розробник буде задоволений швидкістю виконання
програмного коду бібліотечних класів. Інтенсивне використання MFC дозволяє
робити все автоматично, докладаючи мінімум зусиль.
Все це дозволяє робити програми з
легким і зрозумілим інтерфейсом для користувачів.
.3
Технічний проект
Алгоритм - це кінцевий набір правив, який визначає
послідовність операцій для вирішення конкретної безлічі завдань і володіє
п'ятьма важливими рисами: кінцівка, визначеність, введення, висновок,
ефективність.
Він містять наступний ряд загальних вимог:
. Завершаємість (кінцівка). При коректно заданих
початкових даних алгоритм повинен завершувати роботу і видавати результат за
кінцеве число кроків. З іншого боку, імовірнісний алгоритм може і ніколи не
видати результат, але вірогідність цього рівна 0.
. Детермінована (визначеність). У кожен момент часу
наступний крок роботи однозначно визначається станом системи. Таким чином,
алгоритм видає один і той же результат (відповідь) для одних і тих же
початкових даних. У сучасному трактуванні у різних реалізацій одного і того ж
алгоритму повинен бути ізоморфний граф. З іншого боку, існують імовірнісні
алгоритми, в яких наступний крок роботи залежить від поточного стану системи і
випадкового числа, що генерується. Проте при включенні методу генерації
випадкових чисел в список «початкових даних», імовірнісний алгоритм стає
підвидом звичайного.
. Введення. Алгоритм повинен мати деяке число вхідних
даних.
. Результативність (висновок) - завершення алгоритму
певними результатами.
. Зрозумілість. Алгоритм для виконавця повинен
включати тільки ті команди, які йому (виконавцеві) доступні, які входять в його
систему команд.
. Масовість. Алгоритм повинен бути застосовний до
різних наборів початкових даних.
Алгоритм програми для курсової роботи має наступний вигляд.
Рис. 1.1 Принципова блок-схема роботи програми
У даній курсовій роботі використовувалася метод найменших
квадратів, тому для пояснення розкриємо його сутність.
чи в матричній формі запису:
зазвичай не існує точного розв'язку, і потрібно знайти такі β, які мінімізують наступну
норму:
Такий розв'язок завжди існує і він є єдиним:
хоч дана формула не є ефективною через необхідність знаходити обернену
матрицю
<#"702000.files/image007.gif">досягає мінімуму в точці в якій похідна
<#"702000.files/image008.gif">
де використано позначення
Також виконуються рівності:
Підставляючи вирази для залишків і їх похідних одержимо
рівність:
Дану рівність можна звести до вигляду:
або в матричній формі:
Чисельні
методи для обчислення розв'язку
Якщо матриця 
є не виродженою
<#"702000.files/image015.gif">,
де R - верхня трикутна матриця
<#"702000.files/image016.gif">
Розв'язок отримаємо в два кроки:
1. Отримаємо 
з
рівняння
2. Підставимо і отримаємо
з
В обох випадках використовуються властивості трикутної
матриці.
Статистичні
властивості
Одним із найважливіших застосувань лінійного МНК є оцінка параметрів
лінійної регресії. Для заданого набору даних 
будується модель:
або в матричній формі:
де: 
В цих формулах β
- вектор параметрів, які оцінюються, наприклад, за допомогою методу найменших
квадратів, а 
- вектор випадкових змінних.
У класичній моделі множинної лінійної регресії приймаються такі умови:
тобто випадкові змінні є гомоскедастичними
<#"702000.files/image019.gif">одержана
методом найменших квадратів володіє властивостями:
· Незміщеність. Оцінка є
незміщеною
<#"702000.files/image029.gif">Справді:
· Коваріаційна матриця оцінки рівна:
Це випливає з того, що
і
· Ефективність. Згідно -теореми Гауса Маркова
<#"702000.files/image035.gif">до безмежності при збільшенні розміру вибірки.
· Якщо додатково припустити нормальність змінних 
то оцінка МНК має розподіл:
В
математичному моделюванні
Нехай ми маємо вибірку початкових даних 
. Функція f - невідома.
Якщо ми знаємо приблизний вигляд функції f(x), то задамо
її у вигляді функціоналу 
, де 
-
невідомі константи.
Нам потрібно мінімізувати відмінності між F та f. Для
цього беруть за міру суму квадратів різниць значень цих функцій у всіх точках xi
і її мінімізують (тому метод так і називається):
Коефіцієнти aj в яких така міра мінімальна
знаходять з системи:
2.
ПРАКТИЧНЕ РІШЕННЯ
2.1
Робочий проект
Як було сказано в попередніх розділах поставлене завдання
буде реалізуватися за допомогою мови програмування С++ і MFC. Для цього досить
написати функції роботи з файлами і текстовими даними і обробники подій для їх
виклику.
Дана програма була реалізована в проекті MFC, на базі Dialog
based, для написання подібних програм дана база дуже зручна, оскільки
розробникові надається майже готова форма додатку, велику частину віконного простору
займає область для побудови власного інтерфейсу. Створювати інтерфейс потрібно
за допомогою спеціального вбудованого конструктора, що має в своєму запасі
безліч готових елементів, властивості яких описані в бібліотеках MFC.
І такі візуальні елементи MFC, як клас CЕdit і CButton,
CListBox.
Клас CEdit дозволяє створити такий елемент управління
Windows, як "текстове поле", який є простим редактором тексту. Він є
прямокутним дочірнім вікном, в яке можна вводити текст. Коли фокус введення
належить текстовому полю, користувач може вводити в нім текст, редагувати його,
переміщати курсор по тексту, виділяти текст, копіювати його в буфер обміну і
назад. Використовуючи клас CEdit, можна створити як багаторядкового редактора
тексту, так і просто поля для введення тексту.
В більшості випадків, особливо коли текстове поле
використовується для поля введення, він функціонує автономно - додаток запрошує
введений текст на момент запиту, ніяк не контролюючи сам процес введення
інформації.
Клас CListBox дозволяє створити такий елемент управління
Windows, як "багаторядкове текстове поле", який використовується для
виведення тексту. Він є прямокутним дочірнім вікном, в яке можна виводити рядки
тексту.
CButton
Клас CButton містить функції для роботи з кнопками Windows.
Кнопка є маленьким, прямокутним дочірнім вікном, яке може знаходитися в двох
станах, що перемикаються клацаннями миші або клавішами клавіатури. Даний
елемент управління може використовуватися самостійно або в групах. Залежно від
типу кнопки пов'язаний з нею текст може розташовуватися усередині даного
елементу управління або поряд з ним. Зміна стану кнопки зазвичай відбивається
при її відображенні на екрані. Типовим прикладом кнопок є прапорці, перемикачі
і прості кнопки. До якого з даних типів кнопок відноситиметься об'єкт класу
CButton, визначається її стилем, що задається у функції Create при його
створенні.
Об'єкт класу CEdit забезпечує функціонування елементу
управління текстового поля Windows. Текстове поле Windows є прямокутне дочірнє
вікно, в яке користувач може вводити текст. Даний елемент управління може
створюватися в шаблоні діалогу або безпосередньо в програмі користувача. У обох
випадках спочатку викликається конструктор класу CEdit, що створює об'єкт
даного класу, а потім викликається функція Create, що створює текстове поле
Windows і що пов'язує його з об'єктом класу CEdit.
Об'єкт класу, похідного від класу CEdit може бути створений
за один крок, якщо в його конструкторі буде викликана функція Create. Об'єкт
класу CEdit успадковує багато можливостей об'єкту класу CWnd. Щоб записати
текст в об'єкт класу Cedit, використовується функція CWnd::SetWindowText, а щоб
рахувати його звідти використовується функція CWnd::GetWindowText. Ці функції
дозволяють записати або рахувати весь текст, що міститься в даному елементі
управління навіть у тому випадку, коли він є багаторядковим. В тому випадку,
якщо даний елемент управління є багаторядковим, в нім можуть використовуватися
наступні функції для роботи з частиною тексту, що міститься в нім:
CEdit::GetLine, CEdit::SetSel, CEdit::GetSel і CEdit::ReplaceSel.
2.2
Реалізація алгоритму
Для реалізації курсової роботи за основу був взятий метод
гауса.
Початок алгоритму.
Для цього ми спочатку вводимо значення х та у,
потім ініціалізуємо масиви в котрі заносимо данні про х та у:
xx[10], yy[10],
*c;k;(TRUE);[0]=m_x1;[1]=m_x2;[2]=m_x3;[3]=m_x4;[4]=m_x5;[5]=m_x6;[6]=m_x7;[7]=m_x8;[8]=m_x9;[9]=m_x10;[0]=m_y1;[1]=m_y2;[2]=m_y3;[3]=m_y4;[4]=m_y5;[5]=m_y6;[6]=m_y7;[7]=m_y8;[8]=m_y9;[9]=m_y10;
По методу гаса потім прораховується прямий хід.
Рис 2.1. Головне меню
Воно містить поле вводу даних.
Рис 2.2. Поле вводу даних
Та поле виводу даних
Рис 2.3. Поле виводу даних
ВИСНОВОК
В результаті виконання даної курсової роботи отримали
програму, яка дозволяє вирішувати складні завдання за допомогою метода
найменших квадратів.
Програма має зручний інтерфейс, що дозволяє застосовувати її
користувачам з початковим рівнем роботи за комп'ютером.
Під час виконання даної роботи були вивчені способи роботи з
файлами, функціями, класами, операторами, циклами, об'єктами класу MFC.
СПИСОК
ЛІТЕРАТУРИ
1. Тихомирова
Ю.В. Самоучитель MFC. - СПб.: БХВ -
Санкт-Петербург, 2000. - 640 с.: ил.
2. Microsoft
Corporation. - MSDN Library 2001
3. Рихтер
Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом
специфики 64-разрядной версии Windows/Пер, с англ. - 4-е изд. - СПб: Питер; М.:
Издательско-торговый дом «Русская Редакция», 2004. - 749 с.: ил.
4. Круглински
Д., Уингоу С., Шеферд Дж. Программирование на Microsoft Visual C++ 6.0 для
профессионалов/Пер, с англ. - СПб: Питер; М.: Издательско-торговый дом «Русская
Редакция», 2004. - 861 с.: ил.
. Вигерс
Карл Разработка требований к программному обеспечению/Пер, с англ. - М.:
Издательско-торговый дом «Русская Редакция», 2004. -576с.: ил.
. Дж.Либерти.
C++. Енциклопедія користувача
. К.Х.Паппас,
У.Х.Мюррей III. ВІДЛАДКА В C++
ДОДАТОК
PryamoiHod(int n, double **a, double
*b)
{v;(int k = 0,i,j,im; k < n - 1;
k++)
{= k;(i = k + 1; i < n; i++)
{(fabs(a[im][k]) < fabs(a[i][k]))
{= i;
}
}(im != k)
{(j = 0; j < n; j++)
{= a[im][j];[im][j] = a[k][j];[k][j]
= v;
}= b[im];[im] = b[k];[k] = v;
}(i = k + 1; i < n; i++)
{= a[i][k]/a[k][k];[i][k] = 0;[i] =
b[i] - v*b[k];(j = k + 1; j < n; j++)
{[i][j] = a[i][j] - v*a[k][j];
}
}
}
}ObratniHod(int n, double **a, double
*b, double *x)
{s = 0;[n - 1] = b[n - 1]/a[n - 1][n
- 1];(int i = n - 2, j; 0 <= i; i--)
{= 0;(j = i + 1; j < n; j++)
{= s+a[i][j]*x[j];
}[i] = (b[i] - s)/a[i][i];
}
}* MNK(double *x, double *y, int n,
int k)
{**a = new double *[k];*b = new
double [k];*c = new double [k];(int m = 0,i,j; m < k; m++)
{[m] = new double[k];(j = 0; j <
k; j++)
{[m][j] = 0;(i = 0; i < n;
i++)[m][j] += pow(x[i],m + j);
}[m] = 0;(i = 0; i < n; i++)[m] +=
pow(x[i],m)*y[i];
}(k, a, b);(k, a, b, c);c;
}CKursakDlg::OnButton1()
{
// TODO: Add your control
notification handler code herexx[10], yy[10],
*c;k;(TRUE);[0]=m_x1;[1]=m_x2;[2]=m_x3;[3]=m_x4;[4]=m_x5;[5]=m_x6;[6]=m_x7;[7]=m_x8;[8]=m_x9;[9]=m_x10;[0]=m_y1;[1]=m_y2;[2]=m_y3;[3]=m_y4;[4]=m_y5;[5]=m_y6;[6]=m_y7;[7]=m_y8;[8]=m_y9;[9]=m_y10;=
new double[10];= MNK(xx, yy, 10, k);str;(int i=0; i<10; i++)
{.Format("%f",c);_c.AddString(str);
}
//m_c.InsertString(0,c);
//UpdateData(FALSE);
}