dichotomie.ts 14.80 KiB
import { BoolIdentity, Debug } from "./base";
import { Nub } from "./nub";
import { ParamDefinition } from "./param/param-definition";
import { ParamDomain, ParamDomainValue } from "./param/param-domain";
import { Interval } from "./util/interval";
import { Message, MessageCode } from "./util/message";
import { Result } from "./util/result";
class SearchInterval extends Interval {
    private _step: number;
    private _dicho: Dichotomie;
    private _targets: Interval;
    constructor(d: Dichotomie, min: number, max: number, s: number) {
        super(min, max);
        if (s === 0) {
            const e = new Message(MessageCode.ERROR_DICHO_NULL_STEP);
            throw e;
        this._step = s;
        this._dicho = d;
    public reverse() {
        this._step = -this._step;
    public growStep(k: number) {
        if (k === 0) {
            const e = new Message(MessageCode.ERROR_DICHO_INVALID_STEP_GROWTH);
            throw e;
        this._step *= k;
    get step() {
        return this._step;
    get targets() {
        if (this._targets === undefined) {
            // @TODO just set _targets to undefined / null ?
            this._targets = new Interval(undefined, undefined);
        return this._targets;
    /**
     * get target value for lower bound
    get targetLower() {
        this.updateTargets();
        // @TODO val1 is not guaranteed to be the lower bound; use .min ?
        return this.targets.val1;
    /**
     * get target value for upper bound
    get targetUpper() {
        this.updateTargets();
        // @TODO val2 is not guaranteed to be the upper bound; use .max ?
        return this.targets.val2;
    public next() {
        if (this._step > 0) {
            this.val1 = this.val2;
7172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
this.val2 += this._step; this.targets.setValues(this.targets.val2, undefined); } else { this.val2 = this.val1; this.val1 += this._step; this.targets.setValues(undefined, this.targets.val1); } } public hasTargetValue(targ: number) { this.updateTargets(); return this.targets.intervalHasValue(targ); } public toString(): string { return super.toString() + " step=" + this._step; } public updateTargets() { let t1 = this.targets.val1; if (t1 === undefined || isNaN(t1)) { t1 = this._dicho.CalculX(this.val1).vCalc; } let t2 = this.targets.val2; if (t2 === undefined || isNaN(t2)) { t2 = this._dicho.CalculX(this.val2).vCalc; } this.targets.setValues(t1, t2); } } /** * calcul par dichotomie * principe : y=f(x1,x2,...), on connait une valeur de y, * on cherche par ex le x2 correspondant, les autres xi étant fixés. * la méthode Equation() calcule analytiquement y=f(xi) */ // tslint:disable-next-line:max-classes-per-file export class Dichotomie extends Debug { /** * définition de la variable de la fonction */ private _paramX: ParamDefinition; /** * nombre d'étapes de recherche de l'intervalle de départ */ private _startIntervalMaxSteps = 60; /** * nombre d'itérations maxi pour la recherche dichotomique */ private _maxIterations: number = 100; private _currentIterations: number; /** * nom du paramètre calculé analytiquement par Equation() */ private analyticalSymbol: string; /** * Construction de la classe. * @param nub Noeud de calcul contenant la méthode de calcul Equation * @param sVarCalc Nom de la variable à calculer * @param targetSymbol nom du paramètre calculé analytiquement par Equation() */ constructor(private nub: Nub, private sVarCalc: string, dbg: boolean = false, targetSymbol?: string) {
141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
super(dbg); this._paramX = this.nub.getParameter(this.sVarCalc); if (targetSymbol === undefined) { this.analyticalSymbol = this.nub.getFirstAnalyticalParameter().symbol; } else { this.analyticalSymbol = targetSymbol; } } public set maxIterations(n: number) { this._maxIterations = Math.max(n, 1); } /** * Valeur inconnue à rechercher */ private get vX(): number { return this._paramX.v; } private set vX(vCalc: number) { this._paramX.v = vCalc; } /** * étapes de recherche de l'intervalle de départ */ get startIntervalMaxSteps() { return this._startIntervalMaxSteps; } set startIntervalMaxSteps(n: number) { this._startIntervalMaxSteps = n; } public CalculX(x: number): Result { this.vX = x; return this.Calcul(); } /** * trouve la valeur x pour y=f(x) avec un y donné * @param rTarget valeur de y * @param rTol tolérance pour l'arrêt de la recherche * @param rInit valeur initiale approximative de x */ public Dichotomie(rTarget: number, rTol: number, rInit: number): Result { // console.log("-----"); // for (let x = 0; x <= 1; x += 0.1) // console.log(this.CalculX(x).vCalc); // console.log("-----"); // recherche de l'intervalle de départ this.debug( "Dichotomie : valeur cible de " + this.analyticalSymbol + "=" + rTarget + ", valeur initiale de " + this.sVarCalc + "=" + rInit ); const r = this.getStartInterval(rTarget, rInit); if (r.ok) { const inter: SearchInterval = r.intSearch; this._currentIterations = 0; // Dichotomie return this.dichoSearch( rTarget, rTol, inter.min, inter.max, inter.targets.getVal(inter.minIndex),
211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280
inter.targets.getVal(inter.maxIndex) ); } else { return new Result(r.res); } } /** * Calcul de l'équation analytique. * @note Wrapper vers this.nub.Equation pour simplifier le code. * On utilise la première variable du tableau des variables pouvant être calculée analytiquement * Il faudra s'assurer que cette première variable correspond à la méthode de calcul la plus rapide */ private Calcul(): Result { const r: Result = this.nub.Equation(this.analyticalSymbol); this.debug( "dicho : Calcul(vX=" + this.sVarCalc + "=" + this.vX + ") -> " + this.analyticalSymbol + "=" + r.vCalc); return r; } /** * Détermine si une fonction est croissante ou décroissante. * @param x point auquel on calcul la dérivée * @param dom domaine de définition de la variable */ private isIncreasingFunction(x: number, dom: Interval): boolean { const epsilon = 1e-8; const bounds = new Interval(x - epsilon, x + epsilon); bounds.setInterval(bounds.intersect(dom)); // au cas où l'on sorte du domaine de la variable de la fonction const y1 = this.CalculX(bounds.min).vCalc; const y2 = this.CalculX(bounds.max).vCalc; return y2 > y1; } /** * recherche l'intervalle contenant la valeur cible * @param rTarget valeur cible * @param intSearch intervalle de départ * @param intMax intervalle maximum (domaine de définition de la variable) */ private searchTarget(rTarget: number, intSearch: SearchInterval, intMax: Interval) { this.debug("searchTarget : Target " + rTarget + " dans " + intSearch.toString()); let n = 0; let ok: boolean = false; do { intSearch.setInterval(intSearch.intersect(intMax)); if (intSearch.length === 0) { break; } if (intSearch.hasTargetValue(rTarget)) { ok = true; break; } intSearch.growStep(2); intSearch.next(); } while (n++ < this._startIntervalMaxSteps); return { ok, intSearch }; } /** * Détermine l'intervalle de recherche initial * @param rTarget valeur cible de la fonction * @param rInit valeur initiale de la variable */ private getStartInterval(rTarget: number, rInit: number): any { this.debug("intervalle de départ");
281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350
const prmDom: ParamDomain = this._paramX.domain; const step = 0.001; // const step = this.nub.prms.Pr.v; const min: number = prmDom.minValue; const max: number = prmDom.maxValue; if (prmDom.domain === ParamDomainValue.NOT_NULL) { if (rInit === 0) { rInit = 1e-8; } } const intMax: Interval = new Interval(min, max); try { intMax.checkValue(rInit); } catch (m) { return { ok: false, res: m }; } // initialisation de l'intervalle de recherche const intSearch1: SearchInterval = new SearchInterval(this, rInit - step / 2, rInit + step / 2, step); // sens de variation de la fonction const inc = this.isIncreasingFunction(rInit, intMax); if (BoolIdentity(this.CalculX(rInit).vCalc > rTarget, inc)) { intSearch1.reverse(); // par ex, la fonction est croissante et la valeur initiale // de la variable a une image par la fonction > valeur cible } // on cherche dans une première direction let a = this.searchTarget(rTarget, intSearch1, intMax); if (a.ok) { return a; } // il se peut que la fonction ne soit pas monotone et qu'il faille chercher dans l'autre direction const oldStepSign = intSearch1.step > 0 ? 1 : -1; const intSearch2 = new SearchInterval(this, rInit + step / 2, rInit + step, step * -oldStepSign); a = this.searchTarget(rTarget, intSearch2, intMax); if (a.ok) { return a; } // gestion de l'erreur // la valeur cible de la fonction est elle trouvable ? let res: Message; let errDomain = false; switch (prmDom.domain) { case ParamDomainValue.INTERVAL: const si: SearchInterval = new SearchInterval(this, intMax.min, intMax.max, 1); errDomain = !si.hasTargetValue(rTarget); break; case ParamDomainValue.POS: case ParamDomainValue.POS_NULL: const y = this.CalculX(1e-8).vCalc; errDomain = inc && (rTarget < y); break; case ParamDomainValue.ANY: break; default: throw new Error("unsupported parameter domain value"); } if (errDomain) { res = new Message(MessageCode.ERROR_DICHO_INIT_DOMAIN);
351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420
res.extraVar.targetSymbol = this.analyticalSymbol; // symbole de la variable calculée par la fonction res.extraVar.targetValue = rTarget; // valeur cible pour la fonction // intervalle de valeurs pour la variable d'entrée de la fonction res.extraVar.variableInterval = intMax.toString(); res.extraVar.variableSymbol = this._paramX.symbol; // symbole de la variable d'entrée de la fonction } else { // Fusion des infos des deux intervalles explorés const intFus: number[] = []; // Signification des indices : 0,1 : minmax target; 2, 3 : variables associées if (isNaN(intSearch1.targets.max) || isNaN(intSearch2.targets.max)) { // bug targets en NaN en prod mais pas en debug pas à pas en explorant les variables intSearch1.updateTargets(); intSearch2.updateTargets(); } if (intSearch1.targets.max > intSearch2.targets.max) { intFus[1] = intSearch1.targets.max; intFus[3] = intSearch1.getVal(intSearch1.targets.maxIndex); } else { intFus[1] = intSearch2.targets.max; intFus[3] = intSearch2.getVal(intSearch2.targets.maxIndex); } if (intSearch1.targets.min < intSearch2.targets.min) { intFus[0] = intSearch1.targets.min; intFus[2] = intSearch1.getVal(intSearch1.targets.minIndex); } else { intFus[0] = intSearch2.targets.min; intFus[2] = intSearch2.getVal(intSearch2.targets.minIndex); } if (intFus[1] < rTarget) { res = new Message(MessageCode.ERROR_DICHO_TARGET_TOO_HIGH); res.extraVar.extremeTarget = intFus[1]; res.extraVar.variableExtremeValue = intFus[3]; } else { res = new Message(MessageCode.ERROR_DICHO_TARGET_TOO_LOW); res.extraVar.extremeTarget = intFus[0]; res.extraVar.variableExtremeValue = intFus[2]; } res.extraVar.variableSymbol = this._paramX.symbol; // symbole de la variable de la fonction res.extraVar.targetSymbol = this.analyticalSymbol; // symbole de la variable calculée par la fonction res.extraVar.targetValue = rTarget; // valeur cible pour la fonction } return { ok: false, res }; } /** * effectue récursivement la recherche dichotomique * @param Xmin valeur min de l'intervalle * @param Xmax valeur max de l'intervalle * @param Y valeur cible de la fonction * @param Ymin valeur de la fonction pour Xmin * @param Ymax valeur de la fonction pour Xmax */ // tslint:disable-next-line:variable-name private dichoSearch(Ytarg: number, rTol: number, Xmin: number, Xmax: number, Ymin: number, Ymax: number): Result { this._currentIterations++; if (this._currentIterations > this._maxIterations) { const r = new Result(); r.globalLog.add(new Message(MessageCode.ERROR_DICHO_CONVERGE)); return r; } this.debug("dichoSearch : yTarget " + Ytarg + " X " + Xmin + "->" + Xmax + " tol " + rTol); // tslint:disable-next-line:variable-name const Xmid = (Xmin + Xmax) / 2; if (Math.abs(Xmin - Xmax) <= rTol) { return new Result(Xmid); }
421422423424425426427428429430431432433434435436437438439440441
// tslint:disable-next-line:variable-name const Ymid = this.CalculX(Xmid).vCalc; if (Ymin < Ymax) { // fonction croissante if (Ytarg > Ymid) { return this.dichoSearch(Ytarg, rTol, Xmid, Xmax, Ymid, Ymax); } // intervalle supérieur return this.dichoSearch(Ytarg, rTol, Xmin, Xmid, Ymin, Ymid); // intervalle inférieur } else { // fonction décroissante if (Ytarg > Ymid) { return this.dichoSearch(Ytarg, rTol, Xmin, Xmid, Ymin, Ymid); } // intervalle inférieur return this.dichoSearch(Ytarg, rTol, Xmid, Xmax, Ymid, Ymax); // intervalle supérieur } } }