\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[brazilian]{babel}
\usepackage{lmodern}
\usetheme{default}
\usecolortheme{beaver}
\usepackage{graphicx,xcolor}
\usepackage{amsmath}


\newcommand{\sen}{\operatorname{sen}}
\newtheorem{definicao}[theorem]{Definição}
\newtheorem{teorema}[theorem]{Teorema}
\newtheorem{solucao}[theorem]{Solução}
\beamertemplatenavigationsymbolsempty

\makeatletter
\def\th@mystyle{%
	\ttfamily 
	\setbeamercolor{block title example}{bg=red!30,fg=black}
	\setbeamercolor{block body example}{bg=red!10,fg=black!80}
	\def\inserttheoremblockenv{exampleblock}
}
\makeatother
\theoremstyle{mystyle}
\newtheorem{algoritmo}[theorem]{Algoritmo}

\title{Método dos Mínimos Quadrados}
\author
{
	Prof. <NAME>	
}
\institute
{
	Departamento de Ciência da Computação\\
	Universidade Federal de São João del-Rei\\
	\texttt{<EMAIL>}
}
\date{}
\logo{\includegraphics[width=0.2\linewidth]{../ufsj-logo-site}}

\begin{document}
	
\begin{frame}[plain]
    \maketitle
\end{frame}

\begin{frame}[plain]
	\frametitle{Sumário}
	\tableofcontents
\end{frame}

\section{Introdução}
	\begin{frame}
		\frametitle{Introdução}	
		\begin{itemize}
			\item Diferentemente das condições para utilizar interpolação, ao levar em conta a existência de erros nos dados obtidos (limitações dos instrumentos de medição, condições experimentais, etc), surgem novos desafios a serem enfrentados
			\item Neste tipo de problemas, o método dos mínimos quadrados é amplamente utilizado
		\end{itemize}
	\end{frame}
	
	\begin{frame}
		\frametitle{Introdução}	
		\begin{itemize}
			\item Para ilustrar a ideia, considere agora o problema de determinar a constante de uma mola. A Lei de Hooke nos diz que o deslocamento de uma mola é proporcional à força nela aplicada. A questão é como encontrar essa constante de proporcionalidade a partir de dados experimentais
			\begin{equation*}
				F = kx
			\end{equation*}
			\item Suponha que possamos realizar vários experimentos medindo forças aplicadas à mola e os seus respectivos deslocamentos
		\end{itemize}
	\end{frame}

	\begin{frame}
		\frametitle{Introdução}	
		O problema consiste em encontrar uma reta que melhor aproxime esses dados. A inclinação da reta irá nos fornecer a constante k da mola
		\begin{figure}
			\centering
			\includegraphics[width=0.7\linewidth]{Figuras/grafico_01}
			\label{fig:grafico01}
		\end{figure}
	\end{frame}


\section{Método dos Mínimo Quadrados}
	\begin{frame}
		\frametitle{Método dos Mínimo Quadrados}	
		\begin{itemize}
			\item  Vamos chamar de $ f (x) $ a função que queremos aproximar por uma outra função $ g (x) $
			\item  Nem sempre temos uma expressão analítica para $ f (x) $		
			\item  No método dos mínimos quadrados (MMQ) partimos da hipótese de que temos algumas informações sobre a forma de $ g (x) $
			\item Poderíamos saber, \textit{através da observação dos dados}, por exemplo, que $ g (x) $ é uma reta, uma parábola ou alguma outra forma específica
		\end{itemize}
	\end{frame}

	\begin{frame}
		\frametitle{Método dos Mínimo Quadrados}	
		\begin{itemize}
			\item  De forma geral, no caso linear, vamos considerar que a aproximação será por uma função do tipo:
			\begin{equation}\label{Eq.0}
				g(x) = c_{0}\phi_{0}(x) + c_{1}\phi_{1}(x) +\ldots+ c_{n}\phi_{n}(x)
			\end{equation}
			sendo $ \phi_{0}(x), \phi_{1}(x),\ldots,\phi_{n}(x) $ \textbf{funções pré estabelecidas}
			\item Neste caso, a linearidade se dá em relação aos parâmetros $ c_{0},c_{1},\ldots,c_{n} $
			\item Exemplo de algumas famílias de funções utilizadas:
			\begin{gather*}
				\phi_{0}(x) = 1;\;\; \phi_{1}(x) = x;\;\; \phi_{2}(x) = x^{2};\ldots\\
				\phi_{0}(x) = \sen(\pi x);\;\; \phi_{1}(x) = \sen(2\pi x);\ldots
			\end{gather*}
		\end{itemize}
	\end{frame}
	
	\begin{frame}
		\frametitle{Método dos Mínimo Quadrados}	
		\begin{itemize}
			\item  Para cada conjunto de coeficientes $ c_{j}, i = 0,1,\ldots,n $, o \textbf{desvio} ou \textbf{resíduo da aproximação} no ponto $ x_{k} $ é dado por:
			\begin{align*}
				r(x_{k}) &= f(x_{k}) - g(x_{k})\\
						 &= f(x_{k}) - [c_{0}\phi_{0}(x_{k}) + c_{1}\phi_{1}(x_{k}) +\ldots+ c_{n}\phi_{n}(x_{k})]\\
						 &= r(x_{k}; c_{0},c_{1},\ldots,c_{n})
			\end{align*}
			sendo assim, precisamos de estabelecer critérios de aproximação para encaminhar o problema da determinação dos parâmetros 	$ c_{0},c_{1},\ldots,c_{n} $ que nos levarão à \textbf{melhor aproximação}.
		\end{itemize}
	\end{frame}
	
	\begin{frame}
		\frametitle{Exemplo}
		\begin{columns}
			\begin{column}{0.5\textwidth} 
				Tendo a seguinte tabela de dados:
				\begin{table}
					\small 
					\centering
					\begin{tabular}{c|ccccc}
						$ x_{i} $ & 0.3 & 2.7 & 4.5 & 5.9 & 7.8 \\
						\hline
						$ y_{i} $ & 1.8 & 1.9 & 3.1 & 3.9 & 3.3  
					\end{tabular}
				\end{table}
			\end{column}
			\begin{column}{0.5\textwidth}
				e seu respectivo gráfico:	
				\begin{figure}
					\centering
					\includegraphics[width=1.0\linewidth]{Figuras/grafico_02}
					\label{fig:grafico02}
				\end{figure}
			\end{column}
		\end{columns}
		Podemos considerar que existe uma relação aproximadamente linear entre as variáveis.
	\end{frame}

	\begin{frame}
		\frametitle{Exemplo}
		Assim, desprezando alguns pontos da tabela e escolhemos 2 deles, podemos utilizar polinômios interpoladores lineares para obter uma solução aproximada:
		\begin{itemize}
			\item  Escolhendo os pontos (0.3,1.8) e (7.8,3.3) teremos $ g_{1}(x) =  1.74 + 0.2x $ 
			\item  Escolhendo os pontos (2.7,1.9) e (5.9,3.9) teremos $ g_{2}(x) =  0.2125 + 0.625x $
		\end{itemize}
		\begin{figure}
			\centering
			\includegraphics[width=0.6\linewidth]{Figuras/grafico_03}
			\label{fig:grafico03}
		\end{figure}	
	\end{frame}
	
	\begin{frame}
		\frametitle{Questionamentos}
		\begin{itemize}
			\item  Qual aproximação é melhor? $ g_{1} (x) $ ou $ g_{2} (x) $?
			\item  Como verificar a qualidade da aproximação?			
		\end{itemize}
	\end{frame}
	
	\begin{frame}
		\frametitle{Exemplo}
		\begin{itemize}
			\item Para obter as aproximações $ g_{1}(x) $ e $ g_{2}(x) $ desprezamos vários dados da tabela para fazer a interpolação, o que não é muito	conveniente de se fazer
			\item Um modo de se verificar a qualidade da aproximação é calculando a soma de todas as distâncias verticais entre $ f (x_{i} ) $ e $ g (x_{i} ) $ (representadas pelas linhas verdes no gráfico a seguir) ao quadrado:			
		\end{itemize}
		\begin{figure}
			\centering
			\includegraphics[width=0.6\linewidth]{Figuras/grafico_04}
			\label{fig:grafico04}
		\end{figure}	
	\end{frame}

	\begin{frame}
		\frametitle{Exemplo}
		Utilizando a seguinte fórmula:
		\begin{equation}\label{Eq.1}
			E^{2} = \sum_{i=1}^{m} r^{2}(x_{i}) = \sum_{i=1}^{m} [f(x_{i}) - g(x_{i})]^{2}
		\end{equation}
		e as seguintes tabelas, é possível calcular a qualidade da aproximação de $ g_{1}(x) $ e $ g_{2}(x) $:
		\begin{table}
			\small 
			\centering
			\begin{tabular}{c|ccc|cc}
				$ x_{i} $ & $ f(x_{i}) $ & $ g_{1}(x_{i}) $ & $ g_{2}(x_{i}) $ & $ r_{1}^{2}(x_{i}) $ & $ r_{2}^{2}(x_{i}) $ \\
				\hline
				\hline
				0.3 & 1.8 & 1.8 & 0.4 & 0 & 1.96\\
				2.7 & 1.9 & 2.78 & 1.9 & 0.144 & 0\\
				4.5 & 3.1 & 2.64 & 3.025 & 0.2116 & 0.0056\\
				5.9 & 3.9 & 2.94 & 3.9 & 0.9604 & 0\\
				7.8 & 3.3 & 3.3 & 2.275 & 0 & 1.051
			\end{tabular}
		\end{table}
	\end{frame}

	\begin{frame}
		\frametitle{Questionamentos}
		\begin{itemize}
			\item  Obtendo $ E^{2}_{1} = 1.316 $ e $ E^{2}_{2} = 3.0166 $, podemos afirmar que $ g_{1}(x) $ se aproxima melhor que $ g_{2}(x) $ 
			\item  Como escolher $ c_{0} $ e $ c_{1} $ de forma que $ E^{2} $ seja mínimo?		
		\end{itemize}
	\end{frame}
	
	\begin{frame}
		\frametitle{Definição - I}
		Antes de partir para águas mais profundas, é importante definir o produto escalar entre funções:
		\begin{equation*}
			<f,g> = \left\lbrace \begin{array}{l}
					\sum_{i=1}^{m} f(x_{i})g(x_{i}), \mbox{ caso discreto} \\
					\int_{a}^{b} f(x)g(x)dx, \mbox{ caso contínuo}
				\end{array} \right. 
		\end{equation*}
	\end{frame}

	\begin{frame}
		\frametitle{Definição - II}
		\begin{itemize}
			\item O método dos mínimos quadrados consiste na procura de	parâmetros ($ c_{0},c_{1},\ldots,c_{n}  $) que minimizem:
			\begin{itemize}
				\item a soma dos quadrados dos resíduos (caso discreto)
				\item a integral da função resíduo ao quadrado (caso contínuo)
			\end{itemize}
		\item Utilizando a notação de produto escalar, podemos escrever:
		\begin{equation*}
			<r,r> = \sum_{i=1}^{m} [r(x_{i})]^{2} = \sum_{i=1}^{m} [f(x_{i}) - g(x_{i})]^{2}
		\end{equation*}
		\end{itemize}
	\end{frame}

\section{Caso Discreto: Linear}

	\begin{frame}
		\frametitle{MMQ - Caso Discreto Linear}
		De forma geral, queremos aproximar $ f(x) $ por
		\begin{equation*}
			g(x) = c_{0}\phi_{0}(x) + c_{1}\phi_{1}(x) +\ldots+ c_{n}\phi_{n}(x)
		\end{equation*}
		sendo $ \phi_{j} $ funções conhecidas. Assim, para encontrar os melhores parâmetros $ c_{0},c_{1},\ldots,c_{n}  $ é preciso minimizar a função com relação aos parâmetros $ c_{j} $:
		\begin{equation}\label{Eq.2}
			<r,r> = \sum_{i=1}^{m} \left[ f(x_{i}) - \sum_{j=0}^{n}c_{j}\phi_{j}(x_{i})\right] ^{2}
		\end{equation}
	\end{frame}

	\begin{frame}[plain]
		Derivando a Eq.\ref{Eq.2} com relação a cada um dos parâmetros $ c_{k} $ e igualando a zero temos:
		\begin{gather*}
			-2\sum_{i=1}^{m} \left[ f(x_{i}) - \sum_{j=0}^{n}c_{j}\phi_{j}(x_{i})\right] \phi_{k}(x_{i}) = 0\\
			\sum_{i=1}^{m}  f(x_{i}) \phi_{k}(x_{i}) - \sum_{i=1}^{m}\left[\sum_{j=0}^{n}c_{j}\phi_{j}(x_{i})\phi_{k}(x_{i})\right] = 0\\
			\sum_{i=1}^{m}\left[\sum_{j=0}^{n}c_{j}\phi_{j}(x_{i})\phi_{k}(x_{i})\right] = 	\sum_{i=1}^{m}  f(x_{i}) \phi_{k}(x_{i}) \\
			\sum_{j=0}^{n}c_{j}\left[\sum_{i=1}^{m}\phi_{j}(x_{i})\phi_{k}(x_{i})\right] = 	\sum_{i=1}^{m}  f(x_{i}) \phi_{k}(x_{i})
		\end{gather*}
	\end{frame}

	\begin{frame}
		\frametitle{MMQ - Caso Discreto Linear}
		Através da notação de produto escalar podemos reescrever a última igualdade como:
		\begin{equation*}
			\sum_{j=0}^{n}c_{j}<\phi_{j},\phi_{k}> = <f,\phi_{k}>, \mbox{para } k = 0,1,\ldots,n
		\end{equation*}
		que é um sistema de equações lineares $ (n + 1)\times(n + 1) $.
	\end{frame}
	
	\begin{frame}
		\frametitle{Caso - n=2}
		Expandindo a expressão anterior para o caso $ n=2 $ temos:
		\begin{gather*}
			<\phi_{0},\phi_{0}>c_{0} + <\phi_{0},\phi_{1}>c_{1} + <\phi_{0},\phi_{2}>c_{2} = <f,\phi_{0}>\\
			<\phi_{1},\phi_{0}>c_{0} + <\phi_{1},\phi_{1}>c_{1} + <\phi_{1},\phi_{2}>c_{2} = <f,\phi_{1}>\\
			<\phi_{2},\phi_{0}>c_{0} + <\phi_{2},\phi_{1}>c_{1} + <\phi_{2},\phi_{2}>c_{2} = <f,\phi_{2}>\\
		\end{gather*}
		ou de forma matricial:
		\begin{equation*}
			\left[ \begin{array}{ccc}
				<\phi_{0},\phi_{0}> & <\phi_{0},\phi_{1}> & <\phi_{0},\phi_{2}>\\
				<\phi_{1},\phi_{0}> & <\phi_{1},\phi_{1}> & <\phi_{1},\phi_{2}>\\
				<\phi_{2},\phi_{0}> & <\phi_{2},\phi_{1}> & <\phi_{2},\phi_{2}>
			\end{array}\right]
		    \left[ \begin{array}{c}
				c_{0}\\
				c_{1}\\
				c_{2}
			\end{array} \right]
	 		= \left[ \begin{array}{c}
				<f,\phi_{0}>\\
				<f,\phi_{1}>\\
				<f,\phi_{2}>
			\end{array} \right]
		\end{equation*}
	\end{frame}
 	
 	\begin{frame}
 		\frametitle{Caso geral}
 		Para caso geral, teremos:
 		\begin{equation*}
 			\left[ \begin{array}{cccc}
 				<\phi_{0},\phi_{0}> & <\phi_{0},\phi_{1}> & \cdots & <\phi_{0},\phi_{n}>\\
 				<\phi_{1},\phi_{0}> & <\phi_{1},\phi_{1}> & \cdots & <\phi_{1},\phi_{n}>\\
 				\vdots & \vdots & \ddots & \vdots\\
 				<\phi_{n},\phi_{0}> & <\phi_{n},\phi_{1}> & \cdots & <\phi_{n},\phi_{n}>
 			\end{array}\right]
 			\left[ \begin{array}{c}
 				c_{0}\\
 				c_{1}\\
 				\vdots\\
 				c_{n}
 			\end{array} \right]
 			= \left[ \begin{array}{c}
 				<f,\phi_{0}>\\
 				<f,\phi_{1}>\\
 				\vdots\\
 				<f,\phi_{n}>
 			\end{array} \right]
 		\end{equation*}
 		o qual é chamado de \textbf{sistema normal} ou \textbf{equações normais}. Observe que a matriz é simétrica, pois $ < f , g > = < g , f > $.
 	\end{frame}
 	
	\begin{frame}
		\frametitle{Exemplo - I}
		Dada a seguinte tabela:
		\begin{table}
			\small 
			\centering
			\begin{tabular}{c|ccccc}
				$ x_{i} $ & 0 & 0.25 & 0.5 & 0.75 & 1.0 \\
				\hline
				$ f(x_{i}) $ & 1 & 1.284 & 1.6487 & 2.117 & 2.7183
			\end{tabular}
		\end{table}
		aproxime $ f (x) $ por um polinômio linear usando o MMQ.
	\end{frame}

	\begin{frame}
		\frametitle{Solução}
		Como queremos encontrar $ g(x) = c_{0}\phi_{0}(x) +c_{1}\phi_{1}(x) $ sendo
		\begin{equation*}
			\phi_{0}(x) = 1, \mbox{ e } \phi_{1}(x) = x
		\end{equation*}
		vamos primeiro montar os vetores que correspondem a avaliação de cada $ \phi_{j}(x) $ nos pontos $ x_{i} $ dados na tabela, tendo o seguinte sistema linear:
		\begin{equation*}
			\left[ \begin{array}{cc}
				<\phi_{0},\phi_{0}> & <\phi_{0},\phi_{1}> \\
				<\phi_{1},\phi_{0}> & <\phi_{1},\phi_{1}> 
			\end{array}\right]
			\left[ \begin{array}{c}
				c_{0}\\
				c_{1}
			\end{array} \right]
			= \left[ \begin{array}{c}
				<f,\phi_{0}>\\
				<f,\phi_{1}>
			\end{array} \right]
		\end{equation*}
	\end{frame}

	\begin{frame}
		\frametitle{Solução}
		Como cada $ \phi_{j}(x) $ deve ser calculado em todos os pontos $ x_{i} $, teremos 
		\begin{equation*}
			\phi_{0} = \left[ \begin{array}{c}
				1\\
				1\\
				1\\
				1\\
				1
			\end{array} \right], \mbox{ e } \phi_{1} = \left[ \begin{array}{c}
			0\\
			0.25\\
			0.5\\
			0.75\\
			1.0
		\end{array} \right]
		\end{equation*}
		E calculando os produtos escalares temos:
		\begin{gather*}
				<\phi_{0},\phi_{0}> = 5;\;\; <\phi_{1},\phi_{0}> = 2.5;\;\; <\phi_{1},\phi_{1}> = 1.875\\
				<f,\phi_{0}> = 8.768;\;\; <f,\phi_{1}> = 5.4514
		\end{gather*}
	\end{frame}

	\begin{frame}
		\frametitle{Solução}
		Resultando no seguinte sistema:
		\begin{equation*}
			\left[ \begin{array}{cc}
				5 &  2.5 \\
				2.5 & 1.875
			\end{array}\right]
			\left[ \begin{array}{c}
				c_{0}\\
				c_{1}
			\end{array} \right]
			= \left[ \begin{array}{c}
				8.768\\
				5.4514
			\end{array} \right]
		\end{equation*}
		cuja solução é o vetor $ \mathbf{c} = \left[ \begin{array}{c}
			0.89968\\
			1.70784
		\end{array} \right]  $, resultando na função:
		\begin{equation*}
			g(x) = 0.89968 + 1.70784x
		\end{equation*}
	\end{frame}

	\begin{frame}
		\begin{figure}
			\centering
			\includegraphics[width=1.0\linewidth]{Figuras/grafico_05}
			\label{fig:grafico05}
		\end{figure}
	\end{frame}

	\begin{frame}
		\frametitle{Exemplo - II}
		Dada a seguinte tabela:
		\begin{table}
			\small 
			\centering
			\begin{tabular}{c|cccc}
				$ x_{i} $ & -1 & 0 & 1 & 2 \\
				\hline
				$ f(x_{i}) $ & 0 & -1 & 0 & 7 
			\end{tabular}
		\end{table}
		aproxime $ f (x) $ por um polinômio quadrático usando o MMQ.
	\end{frame}
	
	\begin{frame}
		\frametitle{Solução}
		Como queremos encontrar $ g(x) = c_{0}\phi_{0}(x) + c_{1}\phi_{1}(x) + c_{2}\phi_{2}(x) $ sendo
		\begin{equation*}
			\phi_{0}(x) = 1,\;\; \phi_{1}(x) = x, \mbox{ e } \phi_{2}(x) = x^{2}
		\end{equation*}
		vamos primeiro montar os vetores que correspondem a avaliação de cada $ \phi_{j}(x) $ nos pontos $ x_{i} $ dados na tabela, tendo o seguinte sistema linear:
		\begin{equation*}
			\left[ \begin{array}{ccc}
				<\phi_{0},\phi_{0}> & <\phi_{0},\phi_{1}> & <\phi_{0},\phi_{2}> \\
				<\phi_{1},\phi_{0}> & <\phi_{1},\phi_{1}> & <\phi_{1},\phi_{2}> \\
				<\phi_{2},\phi_{0}> & <\phi_{2},\phi_{1}> & <\phi_{2},\phi_{2}> 
			\end{array}\right]
			\left[ \begin{array}{c}
				c_{0}\\
				c_{1}\\
				c_{2}
			\end{array} \right]
			= \left[ \begin{array}{c}
				<f,\phi_{0}>\\
				<f,\phi_{1}>\\
				<f,\phi_{2}>
			\end{array} \right]
		\end{equation*}
	\end{frame}
	
	\begin{frame}
		\frametitle{Solução}
		Como cada $ \phi_{j}(x) $ deve ser calculado em todos os pontos $ x_{i} $, teremos 
		\begin{equation*}
			\phi_{0} = \left[ \begin{array}{c}
				1\\
				1\\
				1\\
				1
			\end{array} \right],\; \phi_{1} = \left[ \begin{array}{c}
				-1\\
				0\\
				1\\
				2
			\end{array} \right], \mbox{ e } \phi_{2}(x) = \left[ \begin{array}{c}
				1\\
				0\\
				1\\
				4
			\end{array} \right]
		\end{equation*}
		E calculando os produtos escalares temos:
		\begin{gather*}
			<\phi_{0},\phi_{0}> = 4;\;\; <\phi_{1},\phi_{0}> = 2;\;\; <\phi_{2},\phi_{0}> = 6;\\
			<\phi_{1},\phi_{1}> = 6;\;\; <\phi_{2},\phi_{1}> = 8;\;\; <\phi_{2},\phi_{2}> = 18;\\
			<f,\phi_{0}> = 6;\;\; <f,\phi_{1}> = 14;\;\; <f,\phi_{2}> =28
		\end{gather*}
	\end{frame}
	
	\begin{frame}
		\frametitle{Solução}
		Resultando no seguinte sistema:
		\begin{equation*}
			\left[ \begin{array}{ccc}
				4 & 2 & 6 \\
				2 & 6 & 8 \\
				6 & 8 & 18
			\end{array}\right]
			\left[ \begin{array}{c}
				c_{0}\\
				c_{1}\\
				c_{2}
			\end{array} \right]
			= \left[ \begin{array}{c}
				6\\
				14\\
				28
			\end{array} \right]
		\end{equation*}
		cuja solução é o vetor $ \mathbf{c} = \left[ \begin{array}{c}
			-8/5\\
			1/5\\
			2
		\end{array} \right]  $, resultando na função:
		\begin{equation*}
			g(x) = -8/5 + x/5 + 2x^{2}
		\end{equation*}
	\end{frame}

	\begin{frame}
		\begin{figure}
			\centering
			\includegraphics[width=1.0\linewidth]{Figuras/grafico_06}
			\label{fig:grafico06}
		\end{figure}
	\end{frame}
 
\begin{frame}
	\frametitle{Conclusão}	
	Foram abordados os seguintes assuntos:
	\begin{itemize}
		\item Introdução à aproximação de curvas pelo método dos mínimos quadrados
		\item MMQ - caso linear
	\end{itemize}
\end{frame}


\begin{frame}[plain]
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip
\begin{figure}
	\centering
	\includegraphics[width=0.9\linewidth]{../krillin_v}
	\label{fig:luffyv}
\end{figure}
\end{frame}

\end{document}
