From 746f4333f3d056a45a41a03dd425d5af61873bce Mon Sep 17 00:00:00 2001 From: =?utf8?q?Bj=C3=B8rn=20Rustad?= Date: Thu, 29 Sep 2011 10:58:36 +0200 Subject: [PATCH] Initial commit of report and its python files --- bj_function.py | 11 +++++ rapport.tex | 127 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 138 insertions(+) create mode 100644 bj_function.py create mode 100644 rapport.tex diff --git a/bj_function.py b/bj_function.py new file mode 100644 index 0000000..6eb99fd --- /dev/null +++ b/bj_function.py @@ -0,0 +1,11 @@ +# Calculate function value in point x +def function_g(x, H, b, c): + return -b.T.dot(x) + 0.5 * x.T.dot(H.dot(x)) + (1.0/12.0) * x.T.dot(_C(x,c).dot(x)) + +# Calculate gradient of g in point x +def gradient_g(x, H, b, c): + return -b.T + H.dot(x) + (1.0/3.0) * x.T.dot(_C(x,c)) + +# Calculate hessian of g in point x +def hessian_g(x, H, b, c): + return H + _C(x,c) diff --git a/rapport.tex b/rapport.tex new file mode 100644 index 0000000..f8f2734 --- /dev/null +++ b/rapport.tex @@ -0,0 +1,127 @@ +% Fag: Numerisk matematikk +% Project 1 +% Utført av: Bjørn, Mats og Edvard + +\documentclass[12pt, a4paper]{article} +\usepackage[norsk]{babel} +\usepackage[latin1]{inputenc} +\usepackage{listings} +\usepackage{graphicx} +\usepackage{color} +\usepackage{amssymb, amsmath} +\setcounter{secnumdepth}{0} +\setlength{\textheight}{240mm} +\setlength{\textwidth}{150mm} +\topmargin -5mm +\oddsidemargin 5mm + +\definecolor{orange}{rgb}{1,0.5,0} + +\lstset{ % +language=Python, % the language of the code +basicstyle=\footnotesize, % the size of the fonts that are used for the code +numbers=left, % where to put the line-numbers +numberstyle=\footnotesize, % the size of the fonts that are used for the line-numbers +stepnumber=1, % the step between two line-numbers. If it's 1, each line + % will be numbered +numbersep=5pt, % how far the line-numbers are from the code +backgroundcolor=\color{white}, % choose the background color. You must add \usepackage{color} +%showspaces=false, % show spaces adding particular underscores +%showstringspaces=false, % underline spaces within strings +%showtabs=false, % show tabs within strings adding particular underscores +%frame=single, % adds a frame around the code +tabsize=4, % sets default tabsize to 2 spaces +captionpos=b, % sets the caption-position to bottom +breaklines=true, % sets automatic line breaking +%breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace +%title=\lstname, % show the filename of files included with \lstinputlisting; + % also try caption instead of title +%escapeinside={\%*}{*)}, % if you want to add a comment within your code +%morekeywords={*,...} % if you want to add more keywords to the set +keywordstyle=\color{orange}\bfseries\emph +} + +\begin{document} + +\title{Semester Project 1 TMA4215} +\author{ + KANDIDATNUMMER! \footnote{Skriv noe her.} \\ + Hva med noe her også? +} + +\maketitle +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% SAMMENDRAG % +% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\abstract{ +ABSTRACTABSTBSSTRACTABSTRACTABSTRACT +} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% % +% RESULTATER % +% % +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\section{Resultater} +We used the following data: +\begin{equation} +H = +\begin{bmatrix} +1 & 2 \\ +3 & 4 +\end{bmatrix} +, \mathbf{b} = +\begin{bmatrix} +1 \\ +2 +\end{bmatrix} +, \mathbf{c} = +\begin{bmatrix} +1 \\ +2 +\end{bmatrix}. +\end{equation} +Where the elements of $\mathbf{b}$ are randomly generated numbers from the interval INTERVAL, and the elements of $\mathbf{c}$ are randomly generated positive numbers. + +To generate the nxn matrix, $H$, we first generate a upper triangular nxn matrix $U$. +The elements along the diagonal of $U$ are the square roots of randomly generated positive numbers, and the elements above the diagonal are randomly generated numbers from the interval INTERVAL. +$H = U^{T}U$ is then a symmetric positive definite matrix. + +The function analyzed in this project was + +\begin{equation} +\label{eq:func_g} +g(\mathbf{x}) := -\mathbf{b}^{T}\mathbf{x}+\frac{1}{2}\mathbf{x}^{T}H\mathbf{x}+\frac{1}{12}\mathbf{x}^{T}C(\mathbf{x})\mathbf{x} +\end{equation} + +From equation \ref{eq:func_g} we get + +\begin{equation} +\label{eq:grad_g} +\nabla g(\mathbf{x}) = -\mathbf{b}^{T}+H\mathbf{x}+\frac{1}{3}\mathbf{x}^{T}C(\mathbf{x}), +\end{equation} +\begin{equation} +\label{eq:hess_g} +\nabla^{2}g(\mathbf{x}) = H+C(\mathbf{x}). +\end{equation} + +The three functions, \ref{eq:func_g}, \ref{eq:grad_g} and \ref{eq:hess_g}, are implemented in the Python code below. + +\lstinputlisting[language=Python]{bj_function.py} + +Consider the Hessian $\nabla^{2}g(\mathbf{x})$, and any vector $\mathbf{v} \in \mathbb{R}^{n}_{*}$. +Then we have + +\begin{eqnarray} +\mathbf{v}^{T}(\nabla^{2}g(\mathbf{x}))\mathbf{v} &=& \mathbf{v}^{T}(H+C(\mathbf{x}))\mathbf{v} \nonumber \\ +&=& \mathbf{v}^{T}H(\mathbf{x}))\mathbf{v}+\mathbf{v}^{T}C(\mathbf{x})\mathbf{v}. +\end{eqnarray} +We already know H is positive definite, so $\mathbf{v}^{T}H(\mathbf{x}))\mathbf{v} > 0$. +Since $C(\mathbf{x})$ only has positive entries, we easily see that + +\begin{equation} +\mathbf{v}^{T}C(\mathbf{x})\mathbf{v} = \sum\limits_{i=1}^n c_{i}(v_{i}x_{i})^2 \geq 0 +\end{equation} +Hence $\mathbf{v}^{T}(H+C(\mathbf{x}))\mathbf{v} > 0$, and we see by definition that the Hessian, $\nabla^{2}g(\mathbf{x})$, is positive definite. +\end{document} -- 2.47.3