This shows you the differences between two versions of the page.
— |
gnucap:user:gnucap_nonlinear_solver [2015/12/11 15:39] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | === Gnucap Nonlinear Solver === | ||
+ | |||
+ | This sections will describe my (gserdyuk) analysis of gnucap nonlinear solver, comparison of it to classic Newton notation and notes which will appear on the course of the study. | ||
+ | |||
+ | == Classic Newton Notation == | ||
+ | |||
+ | Let us consider vector system of equations | ||
+ | |||
+ | '' F = Y*X + N(X) + I =0 (1) '' | ||
+ | |||
+ | where | ||
+ | * Y - linear matrix (here - impedance) | ||
+ | * X - unknows (here - node voltages) | ||
+ | * N(X) - currents of nonlinear branches | ||
+ | * I - free vector | ||
+ | |||
+ | To solve that simultaneous equations with newton algorithms: | ||
+ | |||
+ | ''F_c = F(X_c) (2)'' | ||
+ | |||
+ | ''S_c = inv(dF/dX)*F_c; (3)'' | ||
+ | |||
+ | ''X_n = X_c-S_c; (4)'' | ||
+ | |||
+ | * X_c - current vector of independent values | ||
+ | * F_c - current value of nonlinear function (1) | ||
+ | * S_c - step at current iteration | ||
+ | * dF/dX = J - jacobian matrix, calculated at value X_c | ||
+ | * X_n - vector of independent values at next step | ||
+ | |||
+ | Note - this formula does not contain damp factor - it will e considered later | ||
+ | |||
+ | Such series of X_c have to converge to solution point X_* where F(X_*)=0. | ||
+ | |||
+ | == Newton in Gnucap - simplest case == | ||
+ | |||
+ | //Simplest case of Newton method in gnucap - no damping, no incremental calculation.// | ||
+ | |||
+ | Gnucap uses a bit modified formulation of formulas (2) - (4) to solve same equations (1). | ||
+ | |||
+ | '' FG(X) = dN/dX*X_c-N(X)-I; (5) '' | ||
+ | |||
+ | '' FG_c = FG(X_c) ; (6) '' | ||
+ | |||
+ | '' X_n = inv(J)*FG = inv(J)*(dN/dX*X_c-N-I) ; (7) '' | ||
+ | |||
+ | '' J = dF/dX '' | ||
+ | |||
+ | '' where FG, dF/dx, dN/dX and N are calculated in point X_c '' | ||
+ | |||
+ | namely: | ||
+ | - a) Modified error function does not contain linear term Y*X; | ||
+ | - b) Jacobian in gnucap formulation is the same as in original formulation ( dF/dx, not dFG/dx ) ; | ||
+ | - c) solution of equaton (7) gives new X point instead of the newtonian step. | ||
+ | - d) values dN/dX(X_c) - N(X_c) are calculated from each device whoich operation point is changed - so it saves computation resources. | ||
+ | |||
+ | Indeed. Lets make substitutions: | ||
+ | |||
+ | '' X_n = X_c-inv(J)*F = X_c-inv(J)*(I+N+Y*X_c) = '' | ||
+ | |||
+ | '' = inv(J)*J*X_c-inv(J)*(I+N+Y*X_c) = inv(J)*(J*X_c-I-N-Y*X_c) = '' | ||
+ | |||
+ | '' = inv(J)*(dN/dX*X_c+Y*X_c-I-N-Y*X_c) = '' | ||
+ | |||
+ | finally | ||
+ | |||
+ | '' = inv(J)*(dN/dX*X_c-I-N); '' | ||
+ | |||
+ | Where all values J, dN/dX, N are caluclaed in point X_c | ||
+ | Note that | ||
+ | |||
+ | '' J= dF/dX = dN/dX+Y (8) '' | ||
+ | |||
+ | This has some consequences (see below). | ||
+ | |||
+ | == Damping == | ||
+ | Damped Newton instead of update formula (4) uses smaller step: | ||
+ | |||
+ | ''X_n = X_c-k_c*S_c; (9)'' | ||
+ | |||
+ | where k is damping factor. | ||
+ | |||
+ | There is formal proof that process (9) converges globally under certain conditions and keeps quadratic convergence rate if k=1. | ||
+ | |||
+ | I.e. at the some iteration "current", when next point X_n is calculated, reduced step is used. After that, F and J are caclulated exactly at value X_n. | ||
+ | |||
+ | == Damping in Gnucap == | ||
+ | |||
+ | Gnucap implements somehow modified approach here too. | ||
+ | |||
+ | When X_n is calculated, Gnucap computes element parameters at value X_n, but then calculates FG and J as: | ||
+ | |||
+ | ''FG_n = (1-k)*FG(X_c) + k*FG(X_n) (10)'' | ||
+ | |||
+ | ''J_n = (1-k)*J(X_c) + k*J(X_n) (11)'' | ||
+ | |||
+ | Thus FG_c and J_c are linear interpolation between FG(X_c)=FG_c and FG_n | ||
+ | |||
+ | But should be | ||
+ | |||
+ | ''FG_c=FG( (1-k)*X_c+k*X_n ) (12)'' | ||
+ | |||
+ | Same for Jacobian. | ||
+ | |||
+ | This excludes from consideration higher order derivatives of F(X) and (partially) reduces sense of dumping. | ||
+ | |||
+ | //NB. This is my understanding of Gnucap gumping. If somebody have different opinion - please post it here.// | ||
+ | |||
+ | |||
+ | Currently is planned to implement solver which will use 12 instead of 10,11. I will report results of numeric experiments. | ||
+ | |||
+ | |||
+ | == Calculation of Error function and error norm == | ||
+ | |||
+ | To implement linear search along Newtonian direction it is desired to have strict measure - is next point is better than current or not. | ||
+ | Such measure can be F or ||F|| - indeed - at solution point we have F=0 and ||F||=0. | ||
+ | |||
+ | Unfortunately Gnucap formulation does not give F, but rather calculate FG, which does not tend to zero as X_c -> X*. So - new measure has to eb introduced. | ||
+ | |||
+ | To calculate F we can use the following formula: | ||
+ | |||
+ | ''F_c = J_c * X_c - FG (13)'' | ||
+ | |||
+ | This will require keeping original Jacobian matrix. In case of incremental processing it may mean an issue - we will investigate incremental processing later | ||
+ | |||
+ | |||
+ | === Other Sections === | ||
+ | |||
+ | [[NewtonNumericExample1 | Newton Numeric Example ]] - compares standard and modified newton steps; damped step | ||
+ | |||
+ | [[ProgramingDetails | Programing Details ]] - describeы programming details of solver | ||
+ | |||
+ | [[QueuesAndOPtBypass | Queues and OPT::bypass ]] - covers **bypass** mode and queues | ||
+ | |||
+ | |||