182 \end{frame} |
182 \end{frame} |
183 |
183 |
184 \section{Finding Roots} |
184 \section{Finding Roots} |
185 |
185 |
186 \begin{frame}[fragile] |
186 \begin{frame}[fragile] |
187 \frametitle{Roots of $f(x)=0$} |
|
188 \begin{itemize} |
|
189 \item Roots --- values of $x$ satisfying $f(x)=0$ |
|
190 \item $f(x)=0$ may have real or complex roots |
|
191 \item Presently, let's look at real roots |
|
192 \end{itemize} |
|
193 \end{frame} |
|
194 |
|
195 \begin{frame}[fragile] |
|
196 \frametitle{Roots of $f(x)=0$} |
|
197 \begin{itemize} |
|
198 \item Given function $cosx-x^2$ |
|
199 \item First we find \alert{a} root in $(-\pi/2, \pi/2)$ |
|
200 \item Then we find \alert{all} roots in $(-\pi/2, \pi/2)$ |
|
201 \end{itemize} |
|
202 \end{frame} |
|
203 |
|
204 %% \begin{frame}[fragile] |
|
205 %% \frametitle{Fixed Point Method} |
|
206 %% \begin{enumerate} |
|
207 %% \item Convert $f(x)=0$ to the form $x=g(x)$ |
|
208 %% \item Start with an initial value of $x$ and iterate successively |
|
209 %% \item $x_{n+1}=g(x_n)$ and $x_0$ is our initial guess |
|
210 %% \item Iterate until $x_{n+1}-x_n \le tolerance$ |
|
211 %% \end{enumerate} |
|
212 %% \end{frame} |
|
213 |
|
214 %% \begin{frame}[fragile] |
|
215 %% \frametitle{Fixed Point \dots} |
|
216 %% \begin{lstlisting} |
|
217 %% In []: def our_g(x): |
|
218 %% ....: return sqrt(cos(x)) |
|
219 %% ....: |
|
220 %% In []: tolerance = 1e-5 |
|
221 %% In []: while abs(x1-x0)>tolerance: |
|
222 %% ....: x0 = x1 |
|
223 %% ....: x1 = our_g(x1) |
|
224 %% ....: |
|
225 %% In []: x0 |
|
226 %% \end{lstlisting} |
|
227 %% \end{frame} |
|
228 |
|
229 %% \begin{frame}[fragile] |
|
230 %% \frametitle{Bisection Method} |
|
231 %% \begin{enumerate} |
|
232 %% \item Start with the given interval $(-\pi/2, \pi/2)$ ($(a, b)$) |
|
233 %% \item $f(a)\cdot f(b) < 0$ |
|
234 %% \item Bisect the interval. $c = \frac{a+b}{2}$ |
|
235 %% \item Change the interval to $(a, c)$ if $f(a)\cdot f(c) < 0$ |
|
236 %% \item Else, change the interval to $(c, b)$ |
|
237 %% \item Go back to 3 until $(b-a) \le$ tolerance |
|
238 %% \end{enumerate} |
|
239 %% \alert{\typ{tolerance = 1e-5}} |
|
240 %% \end{frame} |
|
241 |
|
242 %% \begin{frame}[fragile] |
|
243 %% \frametitle{Bisection \dots} |
|
244 %% \begin{lstlisting} |
|
245 %% In []: tolerance = 1e-5 |
|
246 %% In []: a = -pi/2 |
|
247 %% In []: b = 0 |
|
248 %% In []: while b-a > tolerance: |
|
249 %% ....: c = (a+b)/2 |
|
250 %% ....: if our_f(a)*our_f(c) < 0: |
|
251 %% ....: b = c |
|
252 %% ....: else: |
|
253 %% ....: a = c |
|
254 %% ....: |
|
255 %% \end{lstlisting} |
|
256 %% \end{frame} |
|
257 |
|
258 %% \begin{frame}[fragile] |
|
259 %% \frametitle{Newton-Raphson Method} |
|
260 %% \begin{enumerate} |
|
261 %% \item Start with an initial guess of x for the root |
|
262 %% \item $\Delta x = -f(x)/f^{'}(x)$ |
|
263 %% \item $ x \leftarrow x + \Delta x$ |
|
264 %% \item Go back to 2 until $|\Delta x| \le$ tolerance |
|
265 %% \end{enumerate} |
|
266 %% \end{frame} |
|
267 |
|
268 %% \begin{frame}[fragile] |
|
269 %% \frametitle{Newton-Raphson \dots} |
|
270 %% \begin{lstlisting} |
|
271 %% In []: def our_df(x): |
|
272 %% ....: return -sin(x)-2*x |
|
273 %% ....: |
|
274 %% In []: delx = 10*tolerance |
|
275 %% In []: while delx > tolerance: |
|
276 %% ....: delx = -our_f(x)/our_df(x) |
|
277 %% ....: x = x + delx |
|
278 %% ....: |
|
279 %% ....: |
|
280 %% \end{lstlisting} |
|
281 %% \end{frame} |
|
282 |
|
283 %% \begin{frame}[fragile] |
|
284 %% \frametitle{Newton-Raphson \ldots} |
|
285 %% \begin{itemize} |
|
286 %% \item What if $f^{'}(x) = 0$? |
|
287 %% \item Can you write a better version of the Newton-Raphson? |
|
288 %% \item What if the differential is not easy to calculate? |
|
289 %% \item Look at Secant Method |
|
290 %% \end{itemize} |
|
291 %% \end{frame} |
|
292 |
|
293 %% \begin{frame}[fragile] |
|
294 %% \frametitle{Initial Estimates} |
|
295 %% \begin{itemize} |
|
296 %% \item Given an interval |
|
297 %% \item How to find \alert{all} the roots? |
|
298 %% \end{itemize} |
|
299 %% \begin{enumerate} |
|
300 %% \item Check for change of signs of $f(x)$ in the given interval |
|
301 %% \item A root lies in the interval where the sign change occurs |
|
302 %% \end{enumerate} |
|
303 %% \end{frame} |
|
304 |
|
305 %% \begin{frame}[fragile] |
|
306 %% \frametitle{Initial Estimates \ldots} |
|
307 %% \begin{lstlisting} |
|
308 %% In []: def our_f(x): |
|
309 %% ....: return cos(x) - x*x |
|
310 %% ....: |
|
311 %% In []: x = linspace(-pi/2, pi/2, 11) |
|
312 %% In []: y = our_f(x) |
|
313 %% \end{lstlisting} |
|
314 %% Get the intervals of x, where sign changes occur |
|
315 %% \end{frame} |
|
316 |
|
317 %% \begin{frame}[fragile] |
|
318 %% \frametitle{Initial Estimates \ldots} |
|
319 %% \begin{lstlisting} |
|
320 %% In []: pos = y[:-1]*y[1:] < 0 |
|
321 %% In []: rpos = zeros(x.shape, dtype=bool) |
|
322 %% In []: rpos[:-1] = pos |
|
323 %% In []: rpos[1:] += pos |
|
324 %% In []: rts = x[rpos] |
|
325 %% \end{lstlisting} |
|
326 %% Now use Newton-Raphson? |
|
327 %% \end{frame} |
|
328 |
|
329 |
|
330 \begin{frame}[fragile] |
|
331 \frametitle{Scipy Methods - \typ{roots}} |
187 \frametitle{Scipy Methods - \typ{roots}} |
332 \begin{itemize} |
188 \begin{itemize} |
333 \item Calculates the roots of polynomials |
189 \item Calculates the roots of polynomials |
334 \end{itemize} |
190 \end{itemize} |
335 \begin{lstlisting} |
191 \begin{lstlisting} |