Newton's Method

01172014, 09:45 PM
Post: #1




Newton's Method
Newton's Method computes the root of a function \( f(x) \) using linear approximations of \( f(x) \) via tangent lines. The formula is
\[ x_{new} = x_{old}  \frac{f(x_{old})}{f'(x_{old})} \] We use F1 to store the formula for \( f(X) \) (note the capital letter for \( X \) ), and F0 to set up a formula for the right hand side. CAS computations currently do not recognize local variables. And global variables are generally evaluated during parsing in a program, since the programs run in the Home view. This causes some issues with passing values and expressions to CAS commands. In the Home view, a symbolic expression is surrounded by singlequotes. So in the first example, we create a symbolic expression and "insert" other symbolic expressions (such as the derivative of a function) by using strings. In the later examples, we pass a single string to the CAS command, which parses the string as if typed from the CAS command line. Since the CAS recognizes functional algebra, we create a formula for F0 by simply operating on the functions themselves (the term id is the identity function \( id(x)=x \)) and completely ignore the dummy variables. Since our desired formula is \[ F0(x):= x  \frac{F1(x)}{F1'(x)} \] then the equivalent function using functional algebra is \[ F0 := id  \frac{F1}{F1'} \] Style 1: Initial attempt as a solution to a specific problem. The function is prestored into F1 in the Function App. The user then runs the command NEWT() from the command line, or from the program catalog, or from the [Toolbox] menu (press the "User" menu option). Code:
Syle 2: Creating a user interface The INPUT() command is used to allow the user to enter their formula, rather than having it already prestored in F1. Code:
Style 3: Functionlike command This style uses functional notation to send inputs to the command NEWT3(). Due to how variables are initialized, this command must be run from the command line. Otherwise, the builtin input screen will prompt for the arguments, and only accept realvalued inputs, and an algebraic expression cannot be entered for f. Usage: NEWT3("X^25", 2.1, .0001, 100); Code:
Style 4: Mix of Style 1 and 3 Usage: Place formula into F1 in the Function App, and run the program NEWT3 either from the command line, the program catalog, or the [Toolbox] interface. Code:
REMARKS: A more userfriendly program would actually preserve the existing formula for F0, if it exists, and restore it so that the user does not lose their previously stored formulas after running our program. To do this, one could implement: Code:
The error trap is to account for the possibility that there may be no preexisting F0 formula. We restore the user's old F0 formula by simply using: Code:
Fortunately, this works even if oldfunc is an empty string. Graph 3D  QPI  SolveSys 

03292014, 06:29 PM
Post: #2




RE: Newton's Method
I have left a few messages on the NEWT program on youtube if you want to catch up on some of the details there.
I am noticing that the NEWT program behaves differently depending on the Entry type selected in the Home Settings. The Entry method selected affects whether I have to use 2 sets of single quotes or only 1 set. 

03302014, 01:47 AM
Post: #3




RE: Newton's Method
(03292014 06:29 PM)FrankiD Wrote: I have left a few messages on the NEWT program on youtube if you want to catch up on some of the details there. I wasn't able to find any comments on Youtube that seem related to this post. Could you provide a specific example of what you have to do in each entry mode? Graph 3D  QPI  SolveSys 

03302014, 02:45 AM
Post: #4




RE: Newton's Method
My calculator (HP Prime) was rebooting when I would run the NEWT program from your 2nd video. Once I formatted the calculator (something I found in the hpmuseum forum), I guess this wiped the original firmware and fixed the reboot (for the most part...it's happened one time after the formatting).
Since then, I have been able to figure out that the NEWT program works differently depending on the Entry method. In settings (ShiftHome), the Entry method can be Textbook, Algebraic or RPN RPN Entry method: Must enter the function as ''X^231'' (double quotes or 2 sets of single quotes) Textbook or Algebraic Entry method: Can enter 'X^231' (single quotes) 

03302014, 02:08 PM
Post: #5




RE: Newton's Method
Did you mean one of the other programs? NEWT() takes its formula from F1.
Graph 3D  QPI  SolveSys 

03302014, 06:25 PM
Post: #6




RE: Newton's Method
Sorry, yes it is the NEW2() program from your "HP Prime  Programming & Newton's Method (Part 2)" video.


04072014, 07:47 PM
Post: #7




RE: Newton's Method
I see what you mean now. The issue is with how INPUT() behaves. Right now, it is quite particular in how it works due to parser used for the Home view, which of course depends on your settings. I imagine that future updates (esp. if they adjust the parser) will probably add in new quirks to commands like INPUT().
Graph 3D  QPI  SolveSys 

01102015, 09:52 PM
(This post was last modified: 01102015 09:57 PM by Snorre.)
Post: #8




RE: Newton's Method
Hello Han,
I was thinking about creating my own Newton approximator for the CAS (based on a program I once wrote for my HP42s). But since you did that already, I'd like to add my thoughts here. Step 1: Take a vector of functions (expressions) f and a vector of variables x \[ \mathbf{f}(\mathbf{x}) = [f_1(x_1,...,x_n), ..., f_m(x_1,...,x_m)] \] and search for a x* so that f(x*)=0. Thus the iteration becomes \[ \mathbf{d}:=\mathbf{J}^{1}\mathbf{f}(\mathbf{x}) \qquad \mathbf{x}_\mathrm{new} := \mathbf{x}  \mathbf{d} \] where J is the Jacobian matrix of f(x), i.e. \[ J_{ij} = \frac{\partial f_i(\mathbf{x})}{\partial x_j} \] Step 2: Since the number of functions may be different from the numbers of variables (m≠n), don't search for an exact solution but for the nearest \[ \mathbf{d}:=(\mathbf{J}' \mathbf{J})^{1} \mathbf{J}' \mathbf{f}(\mathbf{x}) \qquad \mathbf{x}_\mathrm{new} := \mathbf{x}  \mathbf{d} \] where J' means transposition of J. Step 3: Add another threshold (thd) for breaking up iteration, i.e. 1. Stop if iteration count k exceeds maximum: k>kmax 2. Stop if we're near the solution x*: f(x)<thf 3. Stop if our current guess doesn't change: d<thd My first naive attempt is Code: #cas Prints out the current values of f(x) and d. Returns x=[x1,...,xn]. Maybe you want to incorporate the basic approach (I don't even know if it's all correct, but some simple tests where promising) into your program since you're far more experienced with Prime programming (all that fancy interface stuff, error checking, etc.). Greetings 

01102015, 11:01 PM
(This post was last modified: 01102015 11:23 PM by Han.)
Post: #9




RE: Newton's Method
Snorre,
I think your program is fine, but it doesn't match exactly with the math above your code. The math presumes f(x) is a column vector whereas it appears you have a row vector. Strangely the CAS seems to not mind this and allows the multiplication to go through as is. Nice find! I was planning to write something similar (to incorporate into the equation library program), but basically had a few extra lines in mind (that now seem unnecessary). I was thinking it was necessary to transpose the f vector to ensure valid multiplication. The CAS seems to be rather flexible in this respect! Lastly, defining the jacobi as you did vs leaving it untransposed (how I thought about doing it) comes down to deciding between two transposes vs a single transpose (needed prior to taking inverse). I think the latter choice would give a slight speedup in cases where the number of iterations is significantly large. As for experience, I doubt I have any more experience than anyone here  perhaps more chunks of free time to tinker, maybe. Edit: I think there may be a few other ways to exit the iterations. You've listed a few, but we could also exit based on whether maxf(x_i) is within a certain tolerance as suggested by: http://ocw.usu.edu/Civil_and_Environment...Matlab.pdf Graph 3D  QPI  SolveSys 

« Next Oldest  Next Newest »

User(s) browsing this thread: 2 Guest(s)